发布于 由itewqq

[带权二分图][KM算法][模板] SGU252 Railway Communication

为什么模板题都a的这么艰难

调了这么久发现其实原来的就是对的只是样例可以有不同解，蠢的程度也是没谁了。。。

题意就是求DAG上的最小路径覆盖数，而且使得所有路径权值之和最小，而且要输出路径。将每一个点拆成两个点，分别在二分图左右两侧，读入的所有的路都是从左往右。   求最小路径覆盖也就是求最大匹配，而在这一条件下要求总长度最小，将边附上权值求最小权最大匹配即可。由于KM算法求的是最大权最大匹配，所以要将权值取反，除此之外，由于KM算法相当于每一对之间都有连接，所以要把其他边的权值初始化为-INF。

然后就是输出格式的坑，要把每一条路都找出来，找的过程中判定起点终点不能用link[i]，因为KM跑完之后所有的link都不是-1，也就是说需要用边权来判定，然后他还需要记录下每一条路的长度，，真的烦，，，，，

 

//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include

using namespace std;
typedef long long LL;
const int maxn=310+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int nx,ny;
int g[maxn][maxn];
int link[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool  visx[maxn],visy[maxn];
bool dfs(int x)
{
    int tmp;
    visx[x]=true;
    for (int y=1;y<=ny;y++)
    {
        if(visy[y])continue;
        tmp=lx[x]+ly[y]-g[x][y];
        if(!tmp)
        {
            visy[y]=true;
            if(link[y]==-1||dfs(link[y]))
            {
                link[y]=x;
                return true;
            }
        }
        else if(slack[y]>tmp)
            slack[y]=tmp;
    }
    return false;
}

void KM()
{
    memset(link,-1,sizeof(link));
    memset(ly,0,sizeof(ly));
    for (int i=1;i<=nx;i++)
    {
        lx[i]=-INF;
        for (int j=1;j<=ny;j++)
            if(g[i][j]>lx[i])
            lx[i]=g[i][j];
    }

    for (int x=1;x<=nx;x++)
    {
        for (int i=1;i<=ny;i++)
            slack[i]=INF;
        while(true)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x))break;
            int d=INF;
            for (int i=1;i<=ny;i++)
                if(!visy[i]&&d>slack[i])
                    d=slack[i];
            for (int i=1;i<=nx;i++)
                if(visx[i])
                    lx[i]-=d;
            for (int i=1;i<=ny;i++)//wtf? 2?
            {
                if(visy[i])ly[i]+=d;
                else slack[i]-=d;
            }
        }
    }
    return ;
}

int vis[maxn];
int link2[maxn];
int cc[maxn];

int n;
void get()
{
    int cos=0,sz=0;
    memset(link2,-1,sizeof(link2));

    for (int i=1;i<=ny;i++)
    {

        if(g[link[i]][i]!=INF)//error
        {
            link2[link[i]]=i;
        }
    }
    int cur,top=0;
    for (int i=1;i<=nx;i++)
    {
        cur=i;
        if(g[link[i]][i]==-INF&&!vis[i])//start node error
        {
            sz++;
            cc[sz]++;
            vis[cur]=1;
            while(g[cur][link2[cur]]!=-INF)//error
            {
                cos+=g[cur][link2[cur]];
                cur=link2[cur];
                vis[cur]=1;
                cc[sz]++;
            }
        }

    }
    printf("%d %d\n",sz,-cos);
    memset(vis,0,sizeof(vis));
    sz=0;
    for (int i=1;i<=nx;i++)
    {
        cur=i;
        if(g[link[cur]][cur]==-INF&&!vis[cur])//start node
        {
            printf("%d ",cc[++sz]);
            vis[cur]=1;
            printf("%d ",cur);
            while(g[cur][link2[cur]]!=-INF)
            {
                printf("%d ",link2[cur]);
                cur=link2[cur];
                vis[cur]=1;
            }
            puts("");
        }
    }
}


int main()
{
    int m,u,v,w;
    scanf("%d%d",&n,&m);
    nx=ny=n;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
        g[i][j]=-INF;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=-w;
    }
    KM();
    get();
    return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。