HDU3488Tour （KM算法）

题意: 有N个点，M个单向边,现在要你设计N条路线覆盖所有的点,每个点都属于且值属于一个环。（为什么是N条边：和最小生成树为什么有N-1条边是一样的证明）。

解析：每个点都有一个喜欢对象（出度）和被喜欢对象（入度）,故将一个点拆成男点和女点,然后用最佳匹配即可!

坑die：有重边！MMP

相似的题目：1853 3435

（好像还可以用网络流来解决，容我想两天）

HDU3844

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=;

const int inf=0x7ffffff;

int map[maxn][maxn];

int vis1[maxn],vis2[maxn];

int ex1[maxn],ex2[maxn];

int lack[maxn];

int link[maxn];

int ans,n;

int x1[maxn],x2[maxn],y[maxn],y2[maxn];

int Abs(int v){

    if(v<) v=-v;

    return v;

}

bool _bfs(int v)

{

    vis1[v]=true;

    for(int i=;i<=n;i++){

        if(!vis2[i]){

            int tmp=ex1[v]+ex2[i]-map[v][i];

            if(tmp==){

              vis2[i]=true;

              if(!link[i]||_bfs(link[i])){

                 link[i]=v;

                 return true;

              }

            }

            else if(tmp<lack[i]) lack[i]=tmp;

        }

    }

    return false;

}

void _KM()

{

    int t,i,j;

    memset(link,,sizeof(link));

    memset(ex2,,sizeof(ex2));

    for(i=;i<=n;i++){

        ex1[i]=map[i][];

        for(j=;j<=n;j++)

         if(ex1[i]<map[i][j]) ex1[i]=map[i][j];

    }

    for(t=;t<=n;t++){

        for(i=;i<=n;i++) lack[i]=inf;

        while(true){

            memset(vis1,,sizeof(vis1));

            memset(vis2,,sizeof(vis2));

            if(_bfs(t))  break;

            int gap=inf;

            for(i=;i<=n;i++)

             if(!vis2[i]&&lack[i]<gap) gap=lack[i];

            for(i=;i<=n;i++) if(vis1[i]) ex1[i]-=gap;

            for(i=;i<=n;i++) if(vis2[i]) ex2[i]+=gap;

            for(i=;i<=n;i++) if(!vis2[i])lack[i]-=gap;

        }

    }

    ans=;

    for(i=;i<=n;i++)

       ans-=map[link[i]][i];

    ans=ans;

    printf("%d\n",ans);

}

int main()

{

    int i,j,m,T,u,v,w;

    scanf("%d",&T);

    while(T--){

      scanf("%d%d",&n,&m);

      for(i=;i<=n;i++)

       for(j=;j<=n;j++) map[i][j]=inf;

       for(i=;i<=m;i++){

            scanf("%d%d%d",&u,&v,&w);

            if(w<map[u][v]) map[u][v]=w;//消灭重边

       }

       for(i=;i<=n;i++)

        for(j=;j<=n;j++)map[i][j]=-map[i][j];

        _KM();

    }

    return ;

}

HDU1853 ：普通匈牙利算法算是否false得到-1 。

或者直接KM，若有map[link[i]][i]=-inf，即匹配到不存在的边，也得到-1.

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=;

const int inf=0x7ffffff;

int map[maxn][maxn];

int vis1[maxn],vis2[maxn];

int ex1[maxn],ex2[maxn];

int lack[maxn];

int link[maxn];

int ans,n;

bool _bfs2(int v)

{

    vis1[v]=true;

    for(int i=;i<=n;i++){

        if(!vis2[i]&&-map[v][i]!=inf){

              vis2[i]=true;

              if(!link[i]||_bfs2(link[i])){

                 link[i]=v;

                 return true;

              }

        }

    }

    return false;

}

bool _bfs(int v)

{

    vis1[v]=true;

    for(int i=;i<=n;i++){

        if(!vis2[i]){

            int tmp=ex1[v]+ex2[i]-map[v][i];

            if(tmp==){

              vis2[i]=true;

              if(!link[i]||_bfs(link[i])){

                 link[i]=v;

                 return true;

              }

            }

            else if(tmp<lack[i]) lack[i]=tmp;

        }

    }

    return false;

}

void _KM()

{

    int t,i,j;

    memset(link,,sizeof(link));

    for(i=;i<=n;i++){

        memset(vis2,,sizeof(vis2));

        if(!_bfs2(i)){

            printf("-1\n");

            return ;

        }

    }

    memset(link,,sizeof(link));

    memset(ex2,,sizeof(ex2));

    for(i=;i<=n;i++){

        ex1[i]=map[i][];

        for(j=;j<=n;j++)

         if(ex1[i]<map[i][j]) ex1[i]=map[i][j];

    }

    for(t=;t<=n;t++){

        for(i=;i<=n;i++) lack[i]=inf;

        while(true){

            memset(vis1,,sizeof(vis1));

            memset(vis2,,sizeof(vis2));

            if(_bfs(t))  break;

            int gap=inf;

            for(i=;i<=n;i++)

             if(!vis2[i]&&lack[i]<gap) gap=lack[i];

            for(i=;i<=n;i++) if(vis1[i]) ex1[i]-=gap;

            for(i=;i<=n;i++) if(vis2[i]) ex2[i]+=gap;

            for(i=;i<=n;i++) if(!vis2[i])lack[i]-=gap;

        }

    }

    ans=;

    for(i=;i<=n;i++){

       ans-=map[link[i]][i];

    }

    printf("%d\n",ans);

}

int main()

{

    int i,j,m,T,u,v,w;

    while(~scanf("%d%d",&n,&m))

    {

      for(i=;i<=n;i++)

       for(j=;j<=n;j++) map[i][j]=inf;

       for(i=;i<=m;i++){

            scanf("%d%d%d",&u,&v,&w);

            if(w<map[u][v]) map[u][v]=w;//消灭重边

       }

       for(i=;i<=n;i++)

        for(j=;j<=n;j++)map[i][j]=-map[i][j];

       _KM();

    }

    return ;

}

巴特西

HDU3488Tour （KM算法）

最新文章

热门文章