[关闭]
@darkproject 2018-02-14T14:50:13.000000Z 字数 9758 阅读 857

二分图匹配

2018寒假集训

A - Ants (UVA - 1411)

n个白点和黑点，要求将白点和黑点连接起来，每一个线段一端是黑点另一端是白点，其中保证线段不相交。输出每个白点对应的黑点编号。黑白2色分开连可以看作一个二分图，此时最小权完美匹配即是问题的解。最小权完美匹配不会存在边相交的情况，可以画一个四边形，取对角线绝对不是最小的情况。这题卡精度需要注意还有就是if对于高精度的eps比较

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. using namespace std;
  7. const int MAXN = 110;
  8. const double INF = 0xffffffffffff;
  9. const double eps = 1e-6;
  10. struct Node
  11. {
  12.     double x,y;
  13. }Dot1[MAXN],Dot2[MAXN];
  14. double Dist(Node a,Node b)
  15. {
  16.     return -sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  17. }
  19. int N,NX,NY;
  20. double Map[MAXN][MAXN];
  21. int link[MAXN];
  22. double lx[MAXN],ly[MAXN],slack[MAXN];
  23. int visx[MAXN],visy[MAXN];
  25. int FindPath(int u)
  26. {
  27.     visx[u] = 1;
  28.     for(int i = 1; i <= NY; ++i)
  29.     {
  30.         if(visy[i])
  31.             continue;
  32.         double temp = lx[u] + ly[i] - Map[u][i];
  33.         if(fabs(temp) <= eps)
  34.         {
  35.             visy[i] = 1;
  36.             if(link[i] == -1 || FindPath(link[i]))
  37.             {
  38.                 link[i] = u;
  39.                 return 1;
  40.             }
  41.         }
  42.         else
  43.         {
  44.             if(slack[i] > temp)
  45.                 slack[i] = temp;
  46.         }
  47.     }
  48.     return 0;
  49. }
  51. void KM()
  52. {
  53.     memset(lx,0,sizeof(lx));
  54.     memset(ly,0,sizeof(ly));
  55.     memset(link,-1,sizeof(link));
  56.     for(int i = 1; i <= NX; ++i) 
  57.     {
  58.     lx[i] = -INF;
  59.         for(int j = 1; j <= NY; ++j)
  60.             if(Map[i][j] > lx[i])
  61.                 lx[i] = Map[i][j];
  62.     }
  64.     for(int i = 1; i <= NX; ++i)
  65.     {
  66.         for(int j = 1; j <= NY; ++j)
  67.             slack[j] = INF;
  68.         while(1)
  69.         {
  70.             memset(visx,0,sizeof(visx));
  71.             memset(visy,0,sizeof(visy));
  72.             if(FindPath(i))
  73.                 break;
  74.             double d = INF;
  75.             for(int j = 1; j <= NY; ++j)
  76.                 if(!visy[j] && d > slack[j])
  77.                     d = slack[j];
  78.             for(int j = 1; j <= NX; ++j)
  79.                 if(visx[j])
  80.                     lx[j] -= d;
  81.             for(int j = 1; j <= NY; ++j)
  82.             {
  83.                 if(visy[j])
  84.                     ly[j] += d;
  85.                 else
  86.                     slack[j] -= d;
  87.             }
  88.         }
  89.     }
  90. }
  92. int main()
  93. {
  94.     int N;
  95.     while(~scanf("%d",&N))
  96.     {
  97.         memset(Map,0,sizeof(Map));
  98.         for(int i = 1; i <= N; ++i)
  99.             scanf("%lf%lf",&Dot1[i].x,&Dot1[i].y);
  100.         for(int i = 1; i <= N; ++i)
  101.             scanf("%lf%lf",&Dot2[i].x,&Dot2[i].y);
  103.         for(int i = 1; i <= N; ++i)
  104.             for(int j = 1; j <= N; ++j)
  105.                 Map[j][i] = Dist(Dot1[i],Dot2[j]);
  107.         NX = NY = N;
  108.         KM();
  109.         for(int i=1;i<=N;i++)
  110.             printf("%d\n",link[i]);
  111.         printf("\n");
  112.     }
  114.     return 0;
  115. }

B - Golden Tiger Claw (UVA - 11383)

n*n的矩阵，矩阵内每个格子都有一个整数，我们需要对每行每列确定一个整数要求对任意格子w(i,j)<=row(i)+col(j).根据km的性质，格子整数的值w可以看做权值边，而row和col为顶标，km在执行过程中顶标之和肯定大于等于权值，且结束后所有顶标和最小。因此我们只需要执行一遍km输出顶标及顶标和即可。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm> 
  5. using namespace std;
  6. const int maxn = 505; 
  7. const int INF = 0x3f3f3f3f;
  8. int n, nx, ny, w[maxn][maxn];
  9. int match[maxn], lx[maxn], ly[maxn], slack[maxn];
  10. bool visx[maxn], visy[maxn];
  11. bool dfs(int x){
  12.     visx[x] = true;
  13.     for(int y = 1; y <= ny; y++){
  14.         if(visy[y]) continue;
  15.         int t = lx[x] + ly[y] - w[x][y];
  16.         if(t == 0){
  17.             visy[y] = true;
  18.             if(match[y] == -1 || dfs(match[y])){
  19.                 match[y] = x;
  20.                 return true;
  21.             }
  22.         }
  23.         else if(slack[y] > t){ 
  24.             slack[y] = t;
  25.         }
  26.     }return false;
  27. }
  29. void km(){
  30.     nx = ny = n;
  31.     memset(match, -1, sizeof(match));
  32.     memset(ly, 0, sizeof(ly));
  33.     for(int i = 1; i <= nx; i++){ 
  34.         lx[i] = -INF;
  35.         for(int j = 1; j <= ny; j++){
  36.             if(w[i][j] > lx[i]) lx[i] = w[i][j];
  37.         }
  38.     }
  39.     for(int x = 1; x <= nx; x++){
  40.         for(int i = 1; i <= ny; i++){
  41.             slack[i] = INF;
  42.         }
  43.         while(true){
  44.             memset(visx, false, sizeof(visx));
  45.             memset(visy, false, sizeof(visy));
  46.             if(dfs(x)) break;
  47.             int d = INF;
  48.             for(int i = 1; i <= ny; i++){
  49.                 if(!visy[i] && d > slack[i]) d = slack[i];
  50.             }
  51.             for(int i = 1; i <= nx; i++){
  52.                 if(visx[i]) lx[i] -= d;
  53.             }
  54.             for(int i = 1; i <= ny; i++){
  55.                 if(visy[i]) ly[i] += d;
  56.                 else slack[i] -= d;
  57.             }
  58.         }
  59.     }
  60. }
  61. int main(){
  62.     while(scanf("%d", &n) != EOF)
  63.     {
  64.         int mxr=0;
  65.         for(int i=1;i<=n;i++)
  66.             for(int j=1;j<=n;j++)
  67.                 scanf("%d",&w[i][j]);
  68.         km();
  69.         for(int i=1;i<n;i++)
  70.         {
  71.             mxr+=lx[i];
  72.             printf("%d ",lx[i]);
  73.         }
  74.         mxr+=lx[n];
  75.         printf("%d\n",lx[n]);
  76.         for(int i=1;i<n;i++)
  77.         {
  78.             mxr+=ly[i];
  79.             printf("%d ",ly[i]);
  80.         }
  81.         mxr+=ly[n];
  82.         printf("%d\n%d\n",ly[n],mxr);
  83.     }  
  84.     return 0;
  85. }

D - SAM I AM (UVA - 11419)

一个RxC的网格上面放一些目标，而在每行每列的位置我们可以放加农炮，会攻击所在行或列的位置，问至少需要多少个加农炮才能击杀所有目标，输出加农炮的个数和所放位置。我们将每行和每列看作结点，若(x,y)存在目标x向y连边，不难看出这是一个最小点覆盖问题的求解，难点在于输出最小点覆盖集。我们从左边未匹配点沿未匹配边标记点。解集便为左边未标记点+右边已标记点 证明:http://www.matrix67.com/blog/archives/116

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn = 1005;
  7. int check[maxn],linkery[maxn],linkerx[maxn];
  8. int r,c,n,nx,ny;
  9. int map[maxn][maxn],visx[maxn];
  10. bool dfs(int u)
  11. {
  12.     visx[u]=1;
  13.     for(int v=1;v<=c;v++)
  14.     {
  15.         if(map[u][v]&&!check[v])
  16.         {
  17.             check[v]=1;
  18.             if(linkery[v]==-1||dfs(linkery[v]))
  19.             {
  20.                 linkery[v]=u;
  21.                 linkerx[u]=v;
  22.                 return true;
  23.             }
  24.         }
  25.     }
  26.     return false;
  27. }
  28. int hungarian()
  29. {
  30.     int ans=0;
  31.     memset(linkery,-1,sizeof(linkery));
  32.     memset(linkerx,-1,sizeof(linkerx));
  33.     for(int x=1;x<=r;x++)
  34.     {
  35.         memset(check,0,sizeof(check));
  36.         if(dfs(x)) ans++;
  37.     }
  38.     return ans;
  39. }
  40. int main()
  41. {
  42.     while(scanf("%d%d%d",&r,&c,&n))
  43.     {
  44.         if(r==0&&c==0&&n==0) break;
  45.         memset(map,0,sizeof(map));
  46.         int x,y;
  47.         for(int i=0;i<n;i++)
  48.         {
  49.             scanf("%d%d",&x,&y);
  50.             map[x][y]=1;
  51.         }
  52.         printf("%d",hungarian());
  53.         memset(visx,0,sizeof(visx));
  54.         memset(check,0,sizeof(check));
  55.         for(int i=1;i<=r;i++)
  56.             if(linkerx[i]==-1) dfs(i);
  57.         for(int i=1;i<=r;i++)
  58.             if(!visx[i]) printf(" r%d",i);
  59.         for(int i=1;i<=c;i++)
  60.             if(check[i]) printf(" c%d",i);
  61.         printf("\n");
  62.     }
  63.     return 0;
  64. }

F - Taxi Cab Scheme (UVALive - 3126)

已知每个人的出发时间地点和目的地，2个地方距离所要时间为|x1-x2|+|y1-y2|.出租车接客人至少提前1分钟，问至少需要多少辆出租车才能接送完所有的客人。如果能接送客人a后还能接送b则a向b连边，可以得到一个DAG，接下来求解DAG上的最小边覆盖即可。DAG的最小边覆盖就点拆分为与若图G中有i->j,则i->j`，结果为原图结点数-现图最大匹配数。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. using namespace std;
  7. const int maxn =505;
  8. int m,a[maxn],b[maxn],c[maxn],d[maxn];
  9. int map[maxn][maxn],check[maxn],linker[maxn];
  10. int w[maxn],cap[maxn];
  11. bool dfs(int u)
  12. {
  13.     for(int v=1;v<=m;v++)
  14.     {
  15.         if(map[u][v]&&!check[v])
  16.         {
  17.             check[v]=1;
  18.             if(linker[v]==-1||dfs(linker[v]))
  19.             {
  20.                 linker[v]=u;
  21.                 return true;
  22.             }
  23.         }
  24.     }
  25.     return false;
  26. }
  27. int hungarian()
  28. {
  29.     int ans=0;
  30.     memset(linker,-1,sizeof(linker));
  31.     for(int i=1;i<=m;i++)
  32.     {
  33.         memset(check,0,sizeof(check));
  34.         if(dfs(i)) ans++;
  35.     }
  36.     return ans;
  37. }
  38. int main()
  39. {
  40.     int n;
  41.     scanf("%d",&n);
  42.     while(n--)
  43.     {
  44.         scanf("%d",&m);
  45.         memset(map,0,sizeof(map));
  46.         for(int i=1;i<=m;i++)
  47.         {
  48.             int hh,mm;
  49.             scanf("%d:%d",&hh,&mm);
  50.             cap[i]=hh*60+mm;
  51.             scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
  52.             w[i]=abs(a[i]-c[i])+abs(b[i]-d[i]);
  53.         }
  54.         for(int i=1;i<=m;i++)
  55.             for(int j=i+1;j<=m;j++)
  56.             {
  57.                 if(cap[j]-cap[i]>w[i]+abs(c[i]-a[j])+abs(d[i]-b[j]))
  58.                     map[i][j]=1;
  59.             }
  60.         printf("%d\n",m-hungarian());
  61.     }
  62.     return 0;
  63. }

G - Optimal Bus Route Design (UVALive - 3353)

有n个景点，规划几条bus路线使每个景点仅在一个bus路线中，这个路线必须是环。可以看作n个结点的有向图，每个结点仅在一个环中，求满足这个条件最小的所有环的长度和，如果不存在满足条件的情况则输出N。将有向图结点拆分为i与i`看作二分图，二分图是否有完美匹配可以判断此图是否为环或多环利用km求出最小权完美匹配即可得出需要值，如果无法得到完美匹配则输出N。
ps：这里有WA点，输入有重边，而根据km的原理使用领接矩阵的话会导致边的权值被覆盖，我们这里取最大边的情况即可。也可以改作领接表存储

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm> 
  5. using namespace std;
  6. const int maxn = 505; 
  7. const int INF = 0x3f3f3f3f;
  8. int n, nx, ny, w[maxn][maxn];
  9. int match[maxn], lx[maxn], ly[maxn], slack[maxn];
  10. bool visx[maxn], visy[maxn];
  11. bool dfs(int x){
  12.     visx[x] = true;
  13.     for(int y = 1; y <= ny; y++){
  14.         if(visy[y]) continue;
  15.         int t = lx[x] + ly[y] - w[x][y];
  16.         if(t == 0){
  17.             visy[y] = true;
  18.             if(match[y] == -1 || dfs(match[y])){
  19.                 match[y] = x;
  20.                 return true;
  21.             }
  22.         }
  23.         else if(slack[y] > t){ 
  24.             slack[y] = t;
  25.         }
  26.     }return false;
  27. }
  29. void km(){
  30.     nx = ny = n;
  31.     memset(match, -1, sizeof(match));
  32.     memset(ly, 0, sizeof(ly));
  33.     for(int i = 1; i <= nx; i++){ 
  34.         lx[i] = -INF;
  35.         for(int j = 1; j <= ny; j++){
  36.             if(w[i][j] > lx[i]) lx[i] = w[i][j];
  37.         }
  38.     }
  39.     for(int x = 1; x <= nx; x++){
  40.         for(int i = 1; i <= ny; i++){
  41.             slack[i] = INF;
  42.         }
  43.         while(true){
  44.             memset(visx, false, sizeof(visx));
  45.             memset(visy, false, sizeof(visy));
  46.             if(dfs(x)) break;
  47.             int d = INF;
  48.             for(int i = 1; i <= ny; i++){
  49.                 if(!visy[i] && d > slack[i]) d = slack[i];
  50.             }
  51.             for(int i = 1; i <= nx; i++){
  52.                 if(visx[i]) lx[i] -= d;
  53.             }
  54.             for(int i = 1; i <= ny; i++){
  55.                 if(visy[i]) ly[i] += d;
  56.                 else slack[i] -= d;
  57.             }
  58.         }
  59.     }
  60. }
  61. int main(){
  62.     while(scanf("%d", &n))
  63.     {
  64.         int ans=0;
  65.         int flag=0;
  66.         if(n==0) break;
  67.         for(int i=1;i<=n;i++)//重边考虑
  68.             for(int j=1;j<=n;j++)
  69.                 w[i][j]=-INF;
  70.         for(int i=1;i<=n;i++)
  71.         {
  72.             int a,d;
  73.             while(scanf("%d",&a)){
  74.                 if(a==0) break;
  75.                 scanf("%d",&d);
  76.                 w[i][a]=max(w[i][a],-d);//chongbian
  77.             }
  78.         }
  79.         km();
  80.         for(int i=1;i<=n;i++)
  81.         {
  82.             if(w[match[i]][i]==-INF)
  83.             {
  84.                 flag=1;
  85.                 break;
  86.             }
  87.             ans+=w[match[i]][i];
  88.         }
  89.         if(flag) printf("N\n");
  90.         else printf("%d\n",-ans);
  91.     }  
  92.     return 0;
  93. }

补题：
H - Cat vs. Dog (UVALive - 4288)

有c只猫d只狗，u个投票人，投票人中分为猫党和狗党，他们有keep票和throw out票一张，给出每个人赞同和反对的猫狗。使能满足的投票人的最大个数。这里一眼建图，将每个投票人的赞同的动物和反对动物连边，求最大独立集，但这求的是能留下来的最大动物数。这里应该将投票人作为结点，如果投票人之间有冲突连边，求最大独立集即是最后的解。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. using namespace std;
  7. const int maxn = 505;
  8. const int inf =0x3f3f3f3f;
  9. int t,c,d,u;
  10. int map[maxn][maxn],check[maxn],linker[maxn];
  11. string a[maxn],b[maxn];
  12. bool dfs(int x)
  13. {
  14.     for(int v=1;v<=u;v++)
  15.     {
  16.         if(map[x][v]&&!check[v])
  17.         {
  18.             check[v]=1;
  19.             if(linker[v]==-1||dfs(linker[v]))
  20.             {
  21.                 linker[v]=x;
  22.                 return true;
  23.             }
  24.         }
  25.     }
  26.     return false;
  27. }
  28. int hungarian()
  29. {
  30.     int ans=0;
  31.     memset(linker,-1,sizeof(linker));
  32.     for(int i=1;i<=u;i++)
  33.     {
  34.         memset(check,0,sizeof(check));
  35.         if(dfs(i)) ans++;
  36.     }
  37.     return ans;
  38. }
  39. int main()
  40. {
  41.     scanf("%d",&t);
  42.     while(t--)
  43.     {
  44.         scanf("%d%d%d",&c,&d,&u);
  45.         memset(map,0,sizeof(map));
  46.         for(int i=1;i<=u;i++)
  47.             cin>>a[i]>>b[i];
  48.         for(int i=1;i<=u;i++)
  49.             for(int j=1;j<=u;j++)
  50.                 if(a[i]==b[j]||b[i]==a[j])
  51.                     map[i][j]=map[j][i]=1;
  52.         printf("%d\n",u-hungarian()/2);
  53.     }
  54.     return 0;
  55. }

I - The Great Wall Game (UVALive - 3276)

题意比较简单nxn的方格有n个棋子，求用最小的步数将其摆放为横或纵或斜连着的n颗。暴力km求最小权匹配，将棋子看作结点，棋子之间移动曼哈顿距离看作边权。复杂度O(),具体看代码注释。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath> 
  6. using namespace std;
  7. const int maxn =20;
  8. const int inf =0x3f3f3f3f;
  9. int n,w[maxn][maxn];
  10. int nx,ny,match[maxn],lx[maxn],ly[maxn],slack[maxn];
  11. bool visx[maxn],visy[maxn];
  12. int xx[maxn],yy[maxn];
  13. bool dfs(int x)
  14. {
  15.     visx[x]=true;
  16.     for(int y=1;y<=ny;y++)
  17.     {
  18.         if(visy[y]) continue;
  19.         int t=lx[x]+ly[y]-w[x][y];
  20.         if(t==0)
  21.         {
  22.             visy[y]=true;
  23.             if(match[y]==-1||dfs(match[y]))
  24.             {
  25.                 match[y]=x;
  26.                 return true;
  27.             }
  28.         }
  29.         else if(slack[y]>t)
  30.             slack[y]=t;
  31.     }
  32.     return false;
  33. }
  34. int km()
  35. {
  36.     memset(match,-1,sizeof(match));
  37.     memset(ly,0,sizeof(ly));
  38.     for(int i=1;i<=nx;i++)
  39.     {
  40.         lx[i]=-inf;
  41.         for(int j=1;j<=ny;j++)
  42.             if(w[i][j]>lx[i]) lx[i]=w[i][j];
  43.     }
  44.     for(int x=1;x<=nx;x++)
  45.     {
  46.         for(int i=1;i<=ny;i++)
  47.             slack[i]=inf;
  48.         while(1)
  49.         {
  50.             memset(visx,0,sizeof(visx));
  51.             memset(visy,0,sizeof(visy));
  52.             if(dfs(x)) break;
  53.             int d=inf;
  54.             for(int i=1;i<=ny;i++)
  55.                 if(!visy[i]&&d>slack[i]) d=slack[i];
  56.             for(int i=1;i<=nx;i++)
  57.                 if(visx[i]) lx[i]-=d;
  58.             for(int i=1;i<=ny;i++)
  59.             {
  60.                 if(visy[i]) ly[i]+=d;
  61.                 else slack[i]-=d;
  62.             }
  63.         } 
  64.     }
  65.     int res=0;
  66.     for(int i=1;i<=ny;i++)
  67.         res+=w[match[i]][i];
  68.     return -res;
  69. }
  70. void init()
  71. {
  72.     memset(w,0,sizeof(w));
  73. }
  74. int main()
  75. {
  76.     int cnt=0;
  77.     while(~scanf("%d",&n))
  78.     {
  79.         int ans=inf;
  80.         if(n==0) break;
  81.         nx=ny=n;
  82.         for(int i=1;i<=n;i++)
  83.             scanf("%d%d",&xx[i],&yy[i]);
  84.         for(int i=1;i<=n;i++)//讨论移动行
  85.         {
  86.             init();
  87.             for(int j=1;j<=n;j++)//枚举棋子
  88.                 for(int k=1;k<=n;k++) //讨论移动列
  89.                 {
  90.                     w[j][k]=abs(xx[j]-i)+abs(yy[j]-k);
  91.                     w[j][k]=-w[j][k];
  92.                 }
  93.             ans=min(ans,km());
  94.         }
  95.         for(int i=1;i<=n;i++)//讨论移动列
  96.         {
  97.             init();
  98.             for(int j=1;j<=n;j++)//枚举棋子
  99.                 for(int k=1;k<=n;k++)//讨论移动行
  100.                 {
  101.                     w[j][k]=abs(xx[j]-k)+abs(yy[j]-i);
  102.                     w[j][k]=-w[j][k];
  103.                 }
  104.             ans=min(ans,km());
  105.         }
  106.         init();
  107.         for(int j=1;j<=n;j++)//讨论正斜边
  108.             for(int k=1;k<=n;k++)
  109.             {
  110.                 w[j][k]=abs(xx[j]-k)+abs(yy[j]-k);
  111.                 w[j][k]=-w[j][k];
  112.             }
  113.         ans=min(ans,km());
  114.         init();
  115.         for(int j=1;j<=n;j++)//讨论负斜边
  116.             for(int k=1;k<=n;k++)
  117.             {
  118.                 w[j][k]=abs(xx[j]-k)+abs(yy[j]-(n-k+1));
  119.                 w[j][k]=-w[j][k];
  120.             }
  121.         ans=min(ans,km());
  122.         printf("Board %d: %d moves required.\n\n",++cnt,ans);
  123.     }
  124.     return 0;
  125. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注