博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
大白叔叔专题之匹配、网络流（二）（第一题不是呐~）
阅读量：6716 次
发布时间：2019-06-25

本文共 56929 字，大约阅读时间需要 189 分钟。

1、poj 2195 Going Home（二分图最小权匹配）

　　题意：图上有n个房子，n个人，现在安排每个人回到一所房间，求最小的步数和。

　　思路：KM算法模板题。注意反向。

　　附：推荐km算法大神博客：

　　　　http://blog.sina.com.cn/s/blog_691ce2b701016reh.html

　　　　http://www.cnblogs.com/wenruo/p/5264235.html

　　　　http://blog.csdn.net/sixdaycoder/article/details/47720471

　　　　http://blog.csdn.net/zxn0803/article/details/49999267

　　　　http://www.cnblogs.com/Lanly/p/6291214.html

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 #define N 105  6 #define INF 0x3f3f3f  7 char maze[N][N];  8 int mp[N][N], match[N], lx[N], ly[N], visx[N], visy[N], slack[N];  9 int n, m,ny,nx; 10 //lx,ly为顶标，nx,ny分别为x点集y点集的个数 11 //match数组记录右边y端点所连的左端点x，visx，visy数组记录是否曾访问过，也是判断是否在增广路上 12 struct node 13 { 14     int a, b; 15 }sa[N], sb[N]; 16 //KM求二分图最小匹配模板：只需把权值都变成负的，再用KM算出最大权匹配，然后取反就是答案 17 //学习KM地址http://blog.sina.com.cn/s/blog_691ce2b701016reh.html 18 bool dfs(int x) 19 { 20     visx[x] = 1; 21     for (int y = 1; y <= ny; y++) 22     { 23         if (visy[y]) continue; 24         int t = lx[x] + ly[y] - mp[x][y]; 25         if (t == 0)//(x,y)在相等子图中 26         { 27             visy[y] = 1; 28             if (match[y] == -1 || dfs(match[y])) 29             {
    //注意这里要搜match[y]而不是y，因为我们只搜索x侧的，不需要搜索y侧的  30                 match[y] = x; 31                 return true; 32             } 33         } 34         else if (slack[y]>t) slack[y] = t;//(x,y)不在相等子图中且y不在交错树中slack 取最小的 35     } 36     return false; 37 } 38  39 int KM() 40 { 41     memset(match, -1, sizeof(match)); 42     memset(lx, -INF, sizeof(lx)); 43     memset(ly, 0, sizeof(ly)); 44     for (int i = 1; i <= nx; i++) 45     { 46         for (int j = 1; j <= ny; j++) 47         {
    //lx初始化为与它关联边中最大的 48             if (mp[i][j]>lx[i]) lx[i] = mp[i][j]; 49         } 50     } 51     for (int x = 1; x <= nx; x++) 52     { 53         for (int y = 1; y <= ny; y++) 54             slack[y] = INF; //每次换新的x结点都要初始化slack 55         while (1) 56         { 57             memset(visx, 0, sizeof(visx)); 58             memset(visy, 0, sizeof(visy));//这两个初始化必须放在这里,因此每次dfs()都要更新 59             if (dfs(x)) break; 60             //若成功（找到了增广轨），则该点增广完成，进入下一个点的增广 61             //若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，所有在增广轨中的Y方点的标号全部加上一个常数d. 62             int d = INF; 63             for (int y = 1; y <= ny; y++) 64             { 65                 if (!visy[y] && d>slack[y]) d = slack[y]; 66             } 67             for (int x = 1; x <= nx; x++) 68             { 69                 if (visx[x]) lx[x] -= d; 70             } 71             for (int y = 1; y <= ny; y++) 72             {
    //修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d,这是因为lx[i] 减小了delta,slack[j] = min(lx[i] + ly[j] -w[i][j]) --j不属于交错树--也需要减少delta，第二类边 73                 if (visy[y]) ly[y] += d; 74                 else slack[y] -= d; 75             } 76         } 77     } 78     int res = 0; 79     for (int i = 1; i <= ny; i++) 80     { 81         if (match[i]>-1) res += mp[match[i]][i]; 82     } 83     return res; 84 } 85  86 int main() 87 { 88     int n, m; 89     while (~scanf("%d%d", &n, &m)) 90     { 91         if (n + m == 0) break; 92         for (int i = 1; i <= n; i++) 93         { 94             scanf("%s", maze[i] + 1); 95         } 96         int cnt1 = 0, cnt2 = 0; 97         for (int i = 1; i <= n; i++) 98         { 99             for (int j = 1; j <= m; j++)100             {101                 if (maze[i][j] == 'm')102                 {103                     sa[++cnt1].a = i;104                     sa[cnt1].b = j;105                 }106                 if (maze[i][j] == 'H')107                 {108                     sb[++cnt2].a = i;109                     sb[cnt2].b = j;110                 }111             }112         }113         int cnt = cnt1;114         for (int i = 1; i <= cnt1; i++)115         {116             for (int j = 1; j <= cnt2; j++)117             {118                 mp[i][j] = abs(sa[i].a - sb[j].a) + abs(sa[i].b - sb[j].b);119                 mp[i][j] = -mp[i][j];//取反求最大权匹配（也可以用一个极大值减去原来的值求最大权匹配）120             }121         }122         ny = nx = cnt;123         printf("%d\n", -KM());//再取反则为最小权124     }125     return 0;126 }
View Code

 2、uva 11383 Golden Tiger Claw

　　题意：n*n的矩阵，现在需要确定row和col数组，保证在w(i,j)<=row(i)+col(j)的情况下，求row数组和col数组的和的最小值。

　　思路：二分图完美匹配，KM算法。

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int maxn = 510;  6 const int INF = 0x3f3f3f3f;  7 int mp[maxn][maxn], match[maxn], lx[maxn], ly[maxn], visx[maxn], visy[maxn], slack[maxn];  8 int n, nx, ny;  9 //lx,ly为顶标，nx,ny分别为x点集y点集的个数 10 //match数组记录右边y端点所连的左端点x，visx，visy数组记录是否曾访问过，也是判断是否在增广路上 11 //KM求二分图最小匹配模板：只需把权值都变成负的，再用KM算出最大权匹配，然后取反就是答案 12  13 bool dfs(int x) 14 { 15     visx[x] = 1; 16     for (int y = 1; y <= ny; y++) 17     { 18         if (visy[y]) continue; 19         int t = lx[x] + ly[y] - mp[x][y]; 20         if (t == 0) 21         { 22             visy[y] = 1; 23             if (match[y] == -1 || dfs(match[y])) 24             { 25                 match[y] = x; 26                 return true; 27             } 28         } 29         else if (slack[y] > t) slack[y] = t; 30     } 31     return false; 32 } 33 int KM() 34 { 35     //初始化 36     memset(match, -1, sizeof(match)); 37     memset(lx, - INF, sizeof(lx)); 38     memset(ly, 0, sizeof(ly)); 39     for (int i = 1; i <= nx; i++) 40     { 41         for (int j = 1; j <= ny; j++) 42         { 43             if (mp[i][j] > lx[i]) lx[i] = mp[i][j]; 44         } 45     } 46     for (int x = 1; x <= nx; x++) 47     { 48         for (int y = 1; y <= ny; y++) slack[y] = INF; 49         while (1) 50         { 51             memset(visx, 0, sizeof(visx)); 52             memset(visy, 0, sizeof(visy)); 53             if (dfs(x)) break; 54             int d = INF; 55             for (int y = 1; y <= ny; y++) 56             { 57                 if (!visy[y] && d > slack[y]) d = slack[y]; 58             } 59             for (int x = 1; x <= nx; x++) 60             { 61                 if (visx[x]) lx[x] -= d; 62             } 63             for (int y = 1; y <= ny; y++) 64             { 65                 if (visy[y]) ly[y] += d; 66                 else slack[y] -= d; 67             } 68         } 69     } 70     int res = 0; 71     for (int i = 1; i <= ny; i++) 72     { 73         if (match[i] > -1) res += mp[match[i]][i]; 74     } 75     return res; 76 } 77 int main() 78 { 79     while (~scanf("%d", &n)) 80     { 81         for (int i = 1; i <= n; i++) 82         { 83             for (int j = 1; j <= n; j++) 84             { 85                 scanf("%d", &mp[i][j]); 86                 mp[i][j] = mp[i][j]; 87             } 88         } 89         nx = ny = n; 90         int ans = KM(); 91         for (int i = 1; i <= n; i++) 92         { 93             if (i > 1) printf(" %d", lx[i]); 94             else printf("%d", lx[i]); 95         } 96         printf("\n"); 97         for (int i = 1; i <= n; i++) 98         { 99             if (i > 1) printf(" %d", ly[i]);100             else printf("%d", ly[i]);101         }102         printf("\n");103         printf("%d\n",ans);104     }105     return 0;106 }
View Code

 3、uvalive 2238 Fixed Partition Memory Management

　　题意：有m个内存，n个程序，每个程序对应不同的内存大小有不同的运行时间。该程序对应已知的内存单元的时间为对应的取下线最接近的时间。求所有程序的总结束时间的平均值最小。

　　思路：对于在一个内存中的情况：设该内存中有K个程序。其运行时间分别为t1,t2……tk，则第i个程序结束时间Ti=t1+t2+……+ti，所有程序运行时间之和为kt1+(k-1)t2+(k-2)t3+……+tk。即对于在内存区域j中倒数第p个执行的程序i来说，其对于总的运行时间的贡献为p*Tij，Tij为第i个程序在第j个内存区域内运行的时间。二分图最小权值匹配，KM算法。

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int maxm = 15;  6 const int maxn = 55;  7 const int INF = 0x3f3f3f3f;  8 int mp[maxn][maxn*maxm],lx[maxn],ly[maxn*maxm],slack[maxn*maxm],match[maxn*maxm],visx[maxn],visy[maxn*maxm];  9 int m, n,nx,ny; 10  11 int totmem[maxm]; 12 struct node 13 { 14     int k, mem[maxm], tm[maxm]; 15 }pg[maxn]; 16  17 struct re 18 { 19     int id, l, r; 20 }result[maxn]; 21 bool dfs(int x) 22 { 23     visx[x] = 1; 24     for (int y = 1; y <= ny; y++) 25     { 26         if (visy[y])continue; 27         int t = lx[x] + ly[y] - mp[x][y]; 28         if (t == 0) 29         { 30             visy[y] = 1; 31             if (match[y] == -1 || dfs(match[y])) 32             { 33                 match[y] = x; 34                 return true; 35             } 36         } 37         else if (slack[y] > t) slack[y] = t; 38     } 39     return false; 40 } 41  42 void KM() 43 { 44     memset(match, -1, sizeof(match)); 45     memset(lx, -INF, sizeof(lx)); 46     memset(ly, 0, sizeof(ly)); 47     for (int i = 1; i <= nx; i++) 48     { 49         for (int j = 1; j <= ny; j++) 50         { 51             if (mp[i][j] > lx[i]) lx[i] = mp[i][j]; 52         } 53     } 54  55     for (int x = 1; x <= nx; x++) 56     { 57         for (int y = 1; y <= ny; y++) slack[y] = INF; 58         while (1) 59         { 60             memset(visx, 0, sizeof(visx)); 61             memset(visy, 0, sizeof(visy)); 62  63             if (dfs(x)) break; 64             int d = INF; 65             for (int y = 1; y <= ny; y++) 66             { 67                 if (!visy[y] && d > slack[y]) d = slack[y]; 68             } 69             for (int xx = 1; xx <= nx; xx++) 70             { 71                 if (visx[xx]) lx[xx] -= d; 72             } 73             for (int y = 1; y <= ny; y++) 74             { 75                 if (visy[y]) ly[y]+= d; 76                 else slack[y] -= d; 77             } 78         } 79     } 80 } 81  82 void Oput() 83 { 84     int ans = 0; 85     for (int i = 1; i <= nx; i++) ans += lx[i]; 86     for (int i = 1; i <= ny; i++) ans += ly[i]; 87     printf("Average turnaround time = %.2lf\n", n?-1.0*ans / n:0); 88     int time[11];//记录每个内存当前运行结束时间 89     memset(time, 0, sizeof(time)); 90     for (int i = 1; i <= m; i++) 91     {
    //枚举内存 92         int p; 93         for (p = 1; p <= n; p++) if (match[(i - 1)*n + p]==-1) break;//找到该内存的第一个程序位置 94         for (p = p - 1; p >= 1; --p) 95         { 96             int x = match[(i - 1)*n + p];//所对应的程序 97             result[x].id = i;//程序所对应的内存 98             result[x].l = time[i]; 99             time[i] += (-mp[x][(i - 1)*n + p] / p);100             result[x].r = time[i];101         }102     }103     for (int i = 1; i <= n; i++)104     {105         printf("Program %d runs in region %d from %d to %d\n", i, result[i].id, result[i].l, result[i].r);106     }107 }108 109 110 int main()111 {112     int Case = 1;113     while (~scanf("%d%d", &m, &n)&&n&&m)114     {115         for (int i = 1; i <= m; i++) scanf("%d", &totmem[i]);116         for (int i = 1; i <= n; i++)117         {118             scanf("%d", &pg[i].k);119             for (int j = 1; j <= pg[i].k; j++) scanf("%d%d", &pg[i].mem[j], &pg[i].tm[j]);120         }121         for (int i = 1; i <= n; i++)122         {
    //枚举当前程序123             for (int j = 1; j <= m; j++)124             {
    //枚举当前内存125                 int tmp;//在当前内存的运行时间126                 if (totmem[j] < pg[i].mem[1]) tmp = INF;127                 else128                 {129                     int pos;130                     for (pos = 1; pos <= pg[i].k; pos++)131                     {132                         if (pg[i].mem[pos] > totmem[j]) break;133                     }134                     tmp = pg[i].tm[pos - 1];135                 }136                 for (int k = 1; k <= n; k++)137                 {
    //当前程序在当前内存是倒数第k个程序，则对总时间的贡献为k*tmp138                     if (tmp == INF) mp[i][(j - 1)*n + k] = -INF;139                     else mp[i][(j - 1)*n + k] = -k*tmp;//求最小权匹配，取负140                 }141             }142         }143         nx = n, ny = n*m;144         KM();145         if (Case > 1) printf("\n");146         printf("Case %d\n", Case++);147         Oput();148     }149     return 0;150 }
View Code

 4、uvalive 3989 Ladies' Choice

　　题意：有n个女孩，n个男孩，现在需要匹配出n对男孩和女孩。对于每个女孩，按照喜欢程度有降序的男生order，对于男生也一样。现在要求以女生优先，保证在能匹配全部的情况下，每个女生的选择都是最好的。

　　思路：稳定婚姻问题·稳定匹配·GS算法

1 //稳定婚姻问题 2  3 #include
      
        4 #include
       
         5 #include
        
          6 using namespace std; 7 const int maxn = 1010; 8  9 struct gs//Gale - Shapley算法10 {
    //女士优先11     int n;12     int girl_pre[maxn][maxn];13     int boy_pre[maxn][maxn];14     int girl_match[maxn], boy_match[maxn];15     int next[maxn];16     queue
         
          q;//未开始选择的女孩17 18     void engage(int girl, int boy)19     {
    //匹配20         int pre = boy_match[boy];21         if (pre)22         {23             girl_match[pre] = 0;24             q.push(pre);25         }26         girl_match[girl] = boy;27         boy_match[boy] = girl;28     }29 30     void read()31     {32         scanf("%d", &n);33         for (int i = 1; i <= n; i++)34         {35             for (int j = 1; j <= n; j++) scanf("%d", &girl_pre[i][j]);36             next[i] = 1;//下次等待选择37             girl_match[i] = 0;38             q.push(i);//加入未选择的女生队列39         }40         for (int i = 1; i <= n; i++)41         {42             for (int j = 1; j <= n; j++)43             {44                 int p;45                 scanf("%d", &p);46                 boy_pre[i][p] = j;//在i男生心中p女孩的排名47             }48             boy_match[i] = 0;49         }50     }51 52     void solve()53     {54         while (!q.empty())55         {56             int girl = q.front();57             q.pop();58             int boy = girl_pre[girl][next[girl]++];59             if (!boy_match[boy]) engage(girl, boy);//如果该女孩喜欢的男孩没有被选60             else if (boy_pre[boy][girl] < boy_pre[boy][boy_match[boy]]) engage(girl, boy);//或者该女孩喜欢的男孩的当前匹配的女孩喜欢程度不及该女孩61             else q.push(girl);//等待下次匹配62         }63     }64 65     void print()66     {67         for (int i = 1; i <= n; i++) printf("%d\n", girl_match[i]);68     }69 70 }GS;71 int main()72 {73     int t;74     scanf("%d", &t);75     while (t--)76     {77         GS.read();78         GS.solve();79         GS.print();80         if (t) printf("\n");81     }82 83 84     return 0;85 }
View Code

 5、uva 11419 SAM I AM

　　题意：有R·C的网格，存在N个敌人，现在有一把武器，每一次发射可以消灭一行或一列的敌人，问最少的发射次数，并且给出发射所在的行和列。

　　思路：首先这是一道求最小点覆盖（用最少的点覆盖所有的边）和输出最小点覆盖集的问题。最小点覆盖数=最大匹配数。怎么求最小点覆盖集呢？详见代码注释~

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn = 1010; 6 bool mp[maxn][maxn]; 7 int L_match[maxn], R_match[maxn], visL[maxn], visR[maxn]; 8 int n, nl, nr; 9 bool dfs(int lx)10 {11     visL[lx] = true;12     for (int ly = 1; ly <= nr; ly++)13     {14         if (mp[lx][ly] && !visR[ly])15         {16             visR[ly] = true;17             if (!R_match[ly] || dfs(R_match[ly]))18             {
    //如果当前的ly没有被匹配，或者已经匹配但是和ly匹配的lx'能够和其他ly'匹配，那么当前ly和lx就可以匹配19                 L_match[lx] = ly;20                 R_match[ly] = lx;21                 return true;22             }23         }24     }25     return false;26 }27 28 int maxmatch_XYL()29 {30     int ans = 0;31     memset(L_match, 0, sizeof(L_match));32     memset(R_match, 0, sizeof(R_match));33     for (int i = 1; i <= nl; i++)34     {35         memset(visL, 0, sizeof(visL));36         memset(visR, 0, sizeof(visR));37         if (dfs(i)) ans++;38     }39     return ans;40 }41 int main()42 {43     while (~scanf("%d%d%d", &nl, &nr, &n))44     {45         if (nl == 0 && nr == 0 && n == 0) break;46         memset(mp, 0, sizeof(mp));47         for (int i = 1; i <= n; i++)48         {49             int x, y;50             scanf("%d%d", &x, &y);51             mp[x][y] = true;52         }53         int ans = maxmatch_XYL();54         printf("%d", ans);55         //寻找最小点覆盖集并输出56         memset(visL, 0, sizeof(visL));57         memset(visR, 0, sizeof(visR));58         //从当前未匹配的lx开始dfs,如果有边a（说明原本假设的最小点覆盖集
         <即已匹配的lx>
          不能覆盖到当前dfs到的这一条边），那么原本和边a连接的lx'需更改为a所连接的ly'59         for (int i = 1; i <= nl; i++) if (!L_match[i]) dfs(i);60         for (int i = 1; i <= nl; i++) if (!visL[i]) printf(" r%d", i);//在初期假设的最小点覆盖集中无需删的点61         for (int i = 1; i <= nr; i++) if (visR[i]) printf(" c%d", i);//在dfs过程中lx'更换成的ly'62         printf("\n");63     }64     return 0;65 }
View Code

 6、uvalive 3415 Guardian of Decency

　　题意：如果两个人之间身高差大于40或者同一性别或者喜欢不同的音乐或者喜欢相同的运动，则这两个人可以同时带去出游。问当带出的所有人两两之间至少满足其中一个条件下，所能带走的最多的人？

　　思路：如果两个人4个条件都不符合，那么肯定不能同时带走。现在需要求能带走的最多，则需要最小化不能带走的。当4个条件都不符合时，两人建边，求所选的人两两之间不能连边，即最大独立集问题（选择尽量多的结点，使得任意一条边的两个端点不会同时被选中）。

1 #include
      
         2 #include
         3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const int maxn = 510; 9 map
            
             music; 10 map
             
              sports; 11 struct per 12 { 13 int h; 14 bool isboy; 15 int id_music; 16 int id_sports; 17 }pp[maxn]; 18 19 int n,nl, nr; 20 bool mp[maxn][maxn]; 21 22 int l_match[maxn], r_match[maxn], visl[maxn], visr[maxn]; 23 24 bool dfs(int lx) 25 { 26 visl[lx] = true; 27 for (int ly = 1; ly <= nr; ly++) 28 { 29 if (mp[lx][ly] && !visr[ly]) 30 { 31 visr[ly] = true; 32 if (!r_match[ly] || dfs(r_match[ly])) 33 { 34 l_match[lx] = ly; 35 r_match[ly] = lx; 36 return true; 37 } 38 } 39 } 40 return false; 41 } 42 43 int maxmatch_XYL() 44 { 45 int ans = 0; 46 memset(l_match, 0, sizeof(l_match)); 47 memset(r_match, 0, sizeof(r_match)); 48 for (int i = 1; i <= nl; i++) 49 { 50 memset(visl, 0, sizeof(visl)); 51 memset(visr, 0, sizeof(visr)); 52 if (dfs(i)) ans++; 53 } 54 return ans; 55 } 56 57 bool check(int u, int v) 58 { //四个条件都不满足建边 59 if (abs(pp[u].h - pp[v].h) > 40) 60 return false; 61 else if(pp[u].isboy == pp[v].isboy) 62 return false; 63 else if(pp[u].id_music != pp[v].id_music) 64 return false; 65 else if(pp[u].id_sports == pp[v].id_sports) 66 return false; 67 else return true; 68 } 69 int main() 70 { 71 int t; 72 scanf("%d", &t); 73 while (t--) 74 { 75 scanf("%d", &n); 76 nl = nr = n; 77 memset(mp, 0, sizeof(mp)); 78 music.clear(); 79 sports.clear(); 80 char tmp[110]; 81 for (int i = 1; i <= n; i++) 82 { 83 scanf("%d%s", &pp[i].h,tmp); 84 if (tmp[0] == 'M') pp[i].isboy = true; 85 else pp[i].isboy = false; 86 scanf("%s", tmp); 87 if (!music[tmp]) music[tmp] = music.size() + 1; 88 pp[i].id_music = music[tmp]; 89 scanf("%s", tmp); 90 if (!sports[tmp]) sports[tmp] = sports.size() + 1; 91 pp[i].id_sports = sports[tmp]; 92 } 93 for (int i = 1; i <= nl; i++) 94 { 95 for (int j = i + 1; j <= nr; j++) 96 { 97 if (check(i, j)) mp[i][j]=mp[j][i]=true; 98 } 99 }100 int ans = maxmatch_XYL();101 printf("%d\n", n-ans/2);102 }103 return 0;104 }
View Code

 7、uvalive 3126 Taxi Cab Scheme

　　题意：有n个预约，记录其预约出租车的时间、起始位置、终点位置，并且一辆出租同时只能接送一个预约的乘客。问最少需要多少出租车？

　　思路：如果一辆出租车从第i个预约结束后能赶到第j个预约的地点，且至少能够提前1分钟到，则两点连线。整个问题为有向无环图的最小路径覆盖问题。

最小路径覆盖参考：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int n, nl, nr; 8 const int maxn = 510; 9 bool mp[maxn][maxn];10 int l_match[maxn], r_match[maxn], visl[maxn], visr[maxn];11 bool dfs(int lx)12 {13     visl[lx] = true;14     for (int ly = 1; ly <= nr; ly++)15     {16         if (mp[lx][ly] && !visr[ly])17         {18             visr[ly] = true;19             if (!r_match[ly] || dfs(r_match[ly]))20             {21                 l_match[lx] = ly;22                 r_match[ly] = lx;23                 return true;24             }25         }26     }27     return false;28 }29 30 int maxmatch()31 {32     int ans = 0;33     memset(l_match, 0, sizeof(l_match));34     memset(r_match, 0, sizeof(r_match));35     for (int i = 1; i <= nl; i++)36     {37         memset(visl, 0, sizeof(visl));38         memset(visr, 0, sizeof(visr));39         if (dfs(i)) ans++;40     }41     return ans;42 }43 44 struct node45 {46     int time;47     int start[2];48     int end[2];49     int cost;50 }ps[maxn];51 52 bool check(int from, int to)53 {54     if (ps[from].time + ps[from].cost + abs(ps[to].start[0] - ps[from].end[0]) + abs(ps[to].start[1] - ps[from].end[1]) + 1 <= ps[to].time) return true;55     else return false;56 }57 int main()58 {59     int t;60     scanf("%d", &t);61     while (t--)62     {63         memset(mp, 0, sizeof(mp));64         scanf("%d",&n);65         nl = nr = n;66         for (int i = 1; i <= n; i++)67         {68             int hh, mm;69             char c;70             scanf("%d%c%d", &hh, &c, &mm);71             ps[i].time = hh * 60 + mm;72             scanf("%d%d", &ps[i].start[0], &ps[i].start[1]);73             scanf("%d%d", &ps[i].end[0], &ps[i].end[1]);74             ps[i].cost = abs(ps[i].start[0] - ps[i].end[0]) + abs(ps[i].start[1] - ps[i].end[1]);75         }76         for (int i = 1; i <= n; i++)77         {78             for (int j = 1; j <= n; j++)79             {80                 if (i!=j&&check(i, j)) mp[i][j]  = true;81             }82         }83         int ans = maxmatch();84         printf("%d\n", n - ans);85     }86     return 0;87 }
View Code

 8、uva 11248 Frequency Hopping

　　题意：有n个基站，用有向边相连，问是否可以从1到N有流量至少为C的最大流？没有的话，是否可以增大一条边的容量而达到目的？

　　思路：dicnic求最大流。增大的边肯定选择最小割中的边。在这之后，从求完最大流后的残余网络求其是否满足条件。

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 //Dicnic模板 9 //最小割中，正向边的容量=其流量，逆向边的流量=0。且最小割中所有正向边的容量之和=最大流 10 const int maxn = 110; 11 const int maxe = 10010*2; 12 const int INF = 0x3f3f3f3f; 13 struct edge 14 { 15 int from, to, cap, flow,next;//边的起点、终点、容量、流量、同起点的下一条边的编号 16 edge(int ff=0,int tt=0,int cc=0,int fw=0,int nn=0):from(ff),to(tt),cap(cc),flow(fw),next(nn){ } 17 friend bool operator <(const edge&a, const edge&b) 18 { 19 if (a.from == b.from) 20 { 21 if (a.to < b.to) return true; 22 else return false; 23 } 24 else if (a.from < b.from) return true; 25 else return false; 26 } 27 }Edge[maxe]; 28 int Head[maxn],tmp_head[maxn],totedge; 29 vector
            
             ans; 30 31 struct Dicnic 32 { 33 int n; 34 bool vis[maxn]; 35 int level[maxn]; 36 int st, ed; 37 vector
             
              mincut; 38 int needflow; 39 40 void Init(int nodes,int source,int dest) 41 { 42 n = nodes, st = source, ed = dest; 43 memset(Head, -1, sizeof(Head)); 44 totedge = 0; 45 } 46 47 void addedge(int from, int to, int cap) 48 { 49 Edge[totedge] = edge(from, to, cap, 0, Head[from]); 50 Head[from] = totedge++; 51 Edge[totedge] = edge(to, from, 0, 0, Head[to]); 52 Head[to] = totedge++; 53 } 54 55 bool Dicnic_bfs()//生成层次图 56 { 57 queue
              
               q; 58 int i, u, v; 59 memset(level, -1, sizeof(level)); 60 memset(vis, 0, sizeof(vis)); 61 62 q.push(st); 63 level[st] = 0; 64 vis[st] = true; 65 while (!q.empty()) 66 { 67 u = q.front(); 68 q.pop(); 69 if (u == ed) return true; 70 for (int i = Head[u]; i != -1; i = Edge[i].next) 71 { 72 v = Edge[i].to; 73 if (Edge[i].cap > Edge[i].flow && !vis[v] && level[v] == -1) 74 { //保证这条边有剩余容留，属于残量网络 75 vis[v] = true; 76 level[v] = level[u] + 1; 77 q.push(v); 78 } 79 } 80 } 81 return false; 82 } 83 84 int Dinic_dfs(int u, int maxf) 85 { 86 if (u == ed||maxf==0) return maxf; 87 88 int flow = 0,f; 89 for (int& i = tmp_head[u]; i != -1; i = Edge[i].next) 90 { 91 int v = Edge[i].to; 92 if (Edge[i].cap - Edge[i].flow > 0 && level[v] == level[u] + 1) 93 { 94 f = Dinic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 95 if (f > 0) 96 { 97 Edge[i].flow += f; 98 Edge[i ^ 1].flow -= f; 99 flow += f;100 maxf -= f;101 if (0 == maxf) break;102 if (flow >= needflow) return flow;103 }104 }105 }106 return flow;107 }108 109 int Dinic_maxflow(int needf=INF)//求最大流110 {111 int ret = 0;112 needflow = needf;//需要的流113 while (Dicnic_bfs())114 {115 memcpy(tmp_head, Head, sizeof(Head));116 ret += Dinic_dfs(st, INF);117 if (ret >= needflow) return ret;118 }119 return ret;120 }121 122 void GetMincut()//获得最小割123 {124 mincut.clear();125 for (int i = 0; i < totedge; i++)126 {127 if (vis[Edge[i].from] && !vis[Edge[i].to] && Edge[i].cap > 0) mincut.push_back(i);128 }129 }130 131 void Reduce()//求剩余容量132 {133 for (int i = 0; i < totedge; i++) Edge[i].cap -= Edge[i].flow;134 }135 136 void Clearflow()//把当前流量清零137 {138 for (int i = 0; i < totedge; i++) Edge[i].flow = 0;139 }140 141 }dnc;142 int main()143 {144 int N, E, C;145 int Case = 1;146 while (~scanf("%d%d%d", &N, &E, &C))147 {148 if (N == 0 && E == 0 && C == 0) break;149 dnc.Init(N, 1, N);150 for (int i = 1; i <= E; i++)151 {152 int from, to, cap;153 scanf("%d%d%d", &from, &to, &cap);154 dnc.addedge(from, to, cap);155 }156 int flow = dnc.Dinic_maxflow(C);157 printf("Case %d: ", Case++);158 if (flow >= C) printf("possible\n");159 else160 {161 dnc.GetMincut();162 dnc.Reduce();163 ans.clear();164 int sz = dnc.mincut.size();165 for (int i = 0; i < sz; i++)166 {167 edge &tmp = Edge[dnc.mincut[i]];168 tmp.cap = C;169 dnc.Clearflow();170 if (flow + dnc.Dinic_maxflow(C - flow) >= C) ans.push_back(tmp);171 tmp.cap =0;172 }173 if (ans.empty()) printf("not possible\n");174 else175 {176 sort(ans.begin(), ans.end());177 printf("possible option:");178 sz = ans.size();179 for (int i = 0; i < sz; i++)180 {181 if (i) printf(",");182 printf("(%d,%d)", ans[i].from, ans[i].to);183 }184 printf("\n");185 }186 }187 }188 return 0;189 }
View Code

 9、uvalive 2957 Bring Them There

　　题意：有N个星球，有M条双向边，需要把K台电脑送S星送到T星。每个飞船只能装一台电脑，且从一个星球到达另一个星球的时间为1天。问最少的天数？

　　思路：首先把N个星球看成时序相关。即对于当前天数day,将（day-1）*N+tunnel[i].from和day*N+tunnel[i].to表示第day天可以从tunnel[i].from星前往unnel[i].to星，反过来同样。同时用（day-1）*N+i连到day*N+i表示该飞船第day天停在i星（保证流能传递到下一天）。接着，则是输出，细节看代码注释。（不明白Dicnic算法调用_dfs(st,INF)为什么会出错……）

　　出错原因：因为之后的每一天都是在原来的残留网络上增边再求最大流，原来就有的边的flow并没有被清。所以每次调用最大流得到的流是当天到达目的地的货物数，根据累加性质，DFS的maxf应当置为needflow-ret。以上为maxf应当置为needflow-ret的解释，但对INF（比needflow-ret大得多），为什么不可以还是没有头绪。。。。

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 9 const int maxn = 5010; 10 const int maxe = 501000; 11 const int INF = 0x3f3f3f3f; 12 13 struct edge 14 { 15 int from, to, cap,flow, next; 16 edge(int ff=0,int tt=0,int cc=0,int fw=0,int nn=0):from(ff),to(tt),cap(cc),flow(fw),next(nn){ } 17 }Edge[maxe]; 18 int Head[maxn], tmp_head[maxn], totedge; 19 20 struct Dicnic 21 { 22 int n; 23 bool vis[maxn]; 24 int level[maxn]; 25 int st, ed,needflow; 26 27 void Init(int nodes,int source,int dest) 28 { 29 n = nodes, st = source, ed = dest; 30 memset(Head, -1, sizeof(Head)); 31 totedge = 0; 32 } 33 34 void addedge(int from, int to, int cap) 35 { 36 Edge[totedge] = edge(from, to, cap, 0, Head[from]); 37 Head[from] = totedge++; 38 Edge[totedge] = edge(to, from, 0, 0, Head[to]); 39 Head[to] = totedge++; 40 } 41 42 bool Dicnic_bfs() 43 { 44 queue
            
             q; 45 int i, u, v; 46 memset(level, -1, sizeof(level)); 47 memset(vis, 0, sizeof(vis)); 48 49 q.push(st); 50 level[st] = 0; 51 vis[st] = true; 52 while (!q.empty()) 53 { 54 u = q.front(); 55 q.pop(); 56 57 if (u == ed) return true; 58 for (int i = Head[u]; i != -1; i = Edge[i].next) 59 { 60 v = Edge[i].to; 61 if (Edge[i].cap > Edge[i].flow && !vis[v] && level[v] == -1) 62 { 63 vis[v] = true; 64 level[v] = level[u] + 1; 65 q.push(v); 66 } 67 } 68 } 69 return false; 70 } 71 72 int Dicnic_dfs(int u, int maxf) 73 { 74 if (u == ed || maxf == 0) return maxf; 75 76 int flow = 0, f; 77 for (int &i = tmp_head[u]; i != -1; i = Edge[i].next) 78 { 79 int v = Edge[i].to; 80 if (Edge[i].cap - Edge[i].flow > 0 && level[v] == level[u] + 1) 81 { 82 f = Dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 83 if (f > 0) 84 { 85 Edge[i].flow += f; 86 Edge[i ^ 1].flow -= f; 87 flow += f; 88 maxf -= f; 89 //if (maxf == 0) break; 90 //if (flow >= needflow) return flow; 91 break; 92 } 93 } 94 } 95 if (flow == 0) level[u] = -1; 96 return flow; 97 } 98 99 int Dicnic_maxflow(int ndflow=INF)100 {101 int ret = 0;102 needflow = ndflow;103 while (Dicnic_bfs())104 {105 memcpy(tmp_head, Head, sizeof(Head));106 ret += Dicnic_dfs(st, INF);107 //ret += Dicnic_dfs(st, needlow-ret);108 if (ret >= needflow) return ret;109 }110 return ret;111 }112 113 void set(int nodes,int source, int dest)114 {115 n=nodes,st = source, ed = dest;116 }117 }dnc;118 119 int N, M, K, S, T;120 const int maxm = 210;121 struct tunnel122 {123 int from, to;124 }tnl[maxm];125 const int maxk = 110;126 int prepos[maxk], ismove[maxk], ss[maxk], tt[maxk];127 //prepos[i]表示第i个飞船上一次停留的位置128 //ismove[i]表示第i个飞船当天是否已经飞过（从一个星球飞到另一个星球耗时一天）129 //ss[i],tt[j] 表示当天存在从ss[i]到tt[j]的飞行130 131 bool Cmp(const pair
             
              &a, const pair
              
               &b)132 {133 return a.first < b.first;134 }135 int main()136 {137 while (~scanf("%d%d%d%d%d", &N, &M, &K, &S, &T))138 {139 140 dnc.Init(N, S, T);141 for (int i = 1; i <=M; i++)142 {143 scanf("%d%d", &tnl[i].from, &tnl[i].to);144 }145 //每多加一天新增边146 int sum = 0, day = 0;147 while (sum < K)148 {149 day++;150 for (int i = 1; i <= N; i++) dnc.addedge((day - 1)*N + i, day*N + i, INF);151 for (int i = 1; i <= M; i++)152 {153 dnc.addedge((day - 1)*N + tnl[i].from, day*N + tnl[i].to, 1);154 dnc.addedge((day - 1)*N + tnl[i].to, day*N + tnl[i].from, 1);155 }156 dnc.set(N+day*N,S, T + day*N);157 sum += dnc.Dicnic_maxflow(K - sum);158 }159 //输出答案160 printf("%d\n", day);161 for (int i = 1; i <= K; i++) prepos[i] = S;162 int id = 0;163 for (int d = 1; d <= day; d++)164 {165 id += N*2;//跳过载有计算机的飞船停留在某个星球上一天的边166 int cnt = 0;//记录当天的所有飞行次数167 for (int i = 1; i <= M; i++)168 {169 int flow1 = Edge[id].flow;//从(day - 1)*N + tnl[i].from到day*N + tnl[i].to170 id += 2;171 int flow2 = Edge[id].flow;//从(day - 1)*N + tnl[i].to到day*N + tnl[i].from172 id += 2;173 //flow1和flow2不能同时有流量.如果同时有，说明两艘飞船互换位置，但对总体的进度没有影响174 if (flow1 && !flow2) ss[cnt] = tnl[i].from, tt[cnt++] = tnl[i].to;175 if (flow2 && !flow1) ss[cnt] = tnl[i].to, tt[cnt++] = tnl[i].from;176 }177 memset(ismove, 0, sizeof(ismove));178 printf("%d", cnt);179 vector
               
                
                  >fly;180 for (int i = 0; i < cnt; i++)//对每一个飞行次数，分配给符合条件的飞船181 {182 for (int j = 1; j <= K; j++)183 {184 if (ss[i] == prepos[j] && !ismove[j])185 {186 fly.push_back(make_pair(j, tt[i]));187 //printf(" %d %d", j, tt[i]);188 prepos[j] = tt[i];189 ismove[j] = true;190 break;191 }192 }193 }194 sort(fly.begin(), fly.end(), Cmp);195 for (int i = 0; i < cnt; i++)196 {197 printf(" %d %d", fly[i].first, fly[i].second);198 }199 printf("\n");200 }201 }202 return 0;203 }
View Code

 10、uvalive 2531 The K-League UVALive

　　题意：有n个球队，现在每支球队已经赢了Wi场，输了Di场，并给出两两之间剩余的比赛数，问最后可能胜利的队伍有哪些？

　　思路：首先假设第i个球队剩下的场数全部胜利，则totwin=Wi+sum(…)，那么我们建立一个超级源点和一个超级汇点，从超级源点连到每个匹配（k,j）,容量为其剩余的场数，并记录总剩余场数tot,而每个匹配可以是k胜利或者j胜利，所以连边，容量为INF；然后因为要确保其他队伍j胜利的总场数不超过球队i能够达到的最大胜利场数totwin,则每只球队j连到超级汇点，容量为其所能够胜利的最大场数，即totwin-Wj.最后求最大流，如果最大流刚好等于总剩余场数，说明在所有剩余场数比完之后，球队i可能获胜。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const int maxn = 1010; 9 const int maxe = maxn * 2; 10 const int INF = 0x3f3f3f3f; 11 struct edge 12 { 13 int from, to, cap, flow, next; 14 edge(int ff=0,int tt=0,int cc=0,int ww=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),next(nn){ } 15 }Edge[maxe]; 16 int Head[maxn], tmp_Head[maxn], totedge; 17 18 struct Dicnic 19 { 20 int n,st,ed,needflow; 21 int level[maxn]; 22 int vis[maxn]; 23 24 void Init() 25 { 26 memset(Head, -1, sizeof(Head)); 27 totedge = 0; 28 } 29 30 void Set(int nodes, int source, int dest) 31 { 32 n = nodes, st = source, ed = dest; 33 } 34 35 void addedge(int from, int to, int cap) 36 { 37 Edge[totedge] = edge(from, to, cap, 0, Head[from]); 38 Head[from] = totedge++; 39 Edge[totedge] = edge(to, from, 0, 0, Head[to]); 40 Head[to] = totedge++; 41 } 42 43 bool Dicnic_bfs() 44 { 45 queue
            
             q; 46 int i, u, v; 47 memset(level, -1, sizeof(level)); 48 memset(vis, 0, sizeof(vis)); 49 50 q.push(st); 51 vis[st] = true; 52 level[st] = 0; 53 while (!q.empty()) 54 { 55 u = q.front(); 56 q.pop(); 57 if (u == ed) return true; 58 59 for (int i = Head[u]; i != -1; i = Edge[i].next) 60 { 61 v = Edge[i].to; 62 if (Edge[i].cap > Edge[i].flow && !vis[v] && level[v] == -1) 63 { 64 vis[v] = true; 65 level[v] = level[u] + 1; 66 q.push(v); 67 } 68 } 69 } 70 return false; 71 } 72 73 int Dicnic_dfs(int u, int maxf) 74 { 75 if (u == ed || maxf == 0) return maxf; 76 77 int flow = 0, f; 78 for (int &i = tmp_Head[u]; i != -1; i = Edge[i].next) 79 { 80 int v = Edge[i].to; 81 if (Edge[i].cap > Edge[i].flow&&level[v] == level[u] + 1) 82 { 83 f = Dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 84 if (f > 0) 85 { 86 Edge[i].flow += f; 87 Edge[i ^ 1].flow -= f; 88 flow += f; 89 maxf -= f; 90 if (maxf == 0) break; 91 if (flow >= needflow) return flow; 92 } 93 } 94 } 95 return flow; 96 } 97 98 int Dicnic_maxflow(int ndflow = INF) 99 {100 int ret = 0;101 needflow = ndflow;102 while (Dicnic_bfs())103 {104 memcpy(tmp_Head, Head, sizeof(Head));105 ret += Dicnic_dfs(st, needflow);106 if (ret >= needflow) return ret;107 }108 return ret;109 }110 }dnc;111 112 int win[30], lost[30], remain[30][30];113 vector
             
              canwin;114 int main()115 {116 int t;117 scanf("%d", &t);118 while (t--)119 {120 int n;121 scanf("%d", &n);122 for (int i = 1; i <= n; i++) scanf("%d%d", &win[i], &lost[i]);123 for (int i = 1; i <= n; i++)124 {125 for (int j = 1; j <= n; j++) scanf("%d", &remain[i][j]);126 }127 128 canwin.clear();129 for (int i = 1; i <= n; i++)130 {131 int totwin = win[i];132 for (int j = 1; j <= n; j++) totwin += remain[i][j];133 bool ok = true;134 for (int j = 1; j <= n; j++)135 {136 if (j != i&&win[j] > totwin)137 {138 ok = false;139 break;140 }141 }142 if (!ok) continue;143 144 dnc.Init();145 dnc.Set(n*n + n + 2, 0, n*n + n + 1);146 int full = 0;147 for (int k = 1; k <= n; k++)148 {149 for (int j = k + 1; j <= n; j++)150 {151 full += remain[k][j];152 if (remain[k][j] > 0) dnc.addedge(0, k*n + j, remain[k][j]);153 dnc.addedge(k*n + j, n*n + k, INF);154 dnc.addedge(k*n + j, n*n + j, INF);155 }156 if (totwin > win[k]) dnc.addedge(n*n + k, n*n + n + 1, totwin-win[k]);157 }158 int flow = dnc.Dicnic_maxflow();159 if (flow == full) canwin.push_back(i);160 }161 int sz = canwin.size();162 for (int i = 0; i < sz; i++)163 {164 if (i) printf(" ");165 printf("%d", canwin[i]);166 }167 printf("\n");168 }169 return 0;170 }
View Code

 11、uva 10779 Collectors Problem

　　题意：Bob有n-1个朋友，每个人有Ki张贴纸，贴纸的类型一共有m种。现在，Bob的朋友只会和Bob交换自己没有的贴纸，问Bob最后得到贴纸的种类最大是多少？

　　思路：Bob作为源点，对已经有的贴纸类型建边，容量为其所拥有的该类型的贴纸的数目；每种类型的贴纸向汇点建边，容量为1，表示能否得到该类型的贴纸；当某个朋友拥有某种类型的贴纸的数目大于1时，其可以拿出数目-1这么多的该类型贴纸来交换，则该朋友向该类型贴纸建边，容量为对应数目-1；如果朋友没有某种类型的贴纸，则Bob可以和其交换1张，则该贴纸类型向朋友建边，容量为1.最后用Dicnic求最大流即可。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const int maxn = 110; 9 const int INF = 0x3f3f3f3f; 10 const int maxe = 510; 11 struct edge 12 { 13 int from, to, cap, flow, next; 14 edge(int ff=0,int tt=0,int cc=0,int ww=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),next(nn){ } 15 }Edge[maxe]; 16 int Head[maxn], tmp_head[maxn],totedge; 17 18 struct Dicnic 19 { 20 int n, needflow, st, ed; 21 int level[maxn]; 22 bool vis[maxn]; 23 24 void Init() 25 { 26 memset(Head, -1, sizeof(Head)); 27 totedge = 0; 28 } 29 30 void set(int nodes, int source, int dest) 31 { 32 n = nodes, st = source, ed = dest; 33 } 34 35 void addedge(int from, int to, int cap) 36 { 37 Edge[totedge] = edge(from, to, cap, 0, Head[from]); 38 Head[from] = totedge++; 39 Edge[totedge] = edge(to, from, 0, 0, Head[to]); 40 Head[to] = totedge++; 41 } 42 43 bool Dicnic_bfs() 44 { 45 memset(level, -1, sizeof(level)); 46 memset(vis, 0, sizeof(vis)); 47 48 queue
            
             q; 49 q.push(st); 50 vis[st] = true; 51 level[st] = 0; 52 53 while (!q.empty()) 54 { 55 int u = q.front(); 56 q.pop(); 57 58 if (u == ed) return true; 59 for (int i = Head[u]; i != -1; i = Edge[i].next) 60 { 61 int v = Edge[i].to; 62 if (!vis[v] && Edge[i].cap > Edge[i].flow) 63 { 64 vis[v] = true; 65 level[v] = level[u] + 1; 66 q.push(v); 67 } 68 } 69 } 70 return false; 71 } 72 73 int Dicnic_dfs(int u, int maxf) 74 { 75 if (u == ed || maxf == 0) return maxf; 76 77 int flow = 0, f; 78 for (int& i = tmp_head[u]; i != -1; i = Edge[i].next) 79 { 80 int v = Edge[i].to; 81 if (Edge[i].cap > Edge[i].flow&&level[v] == level[u] + 1) 82 { 83 f = Dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 84 if (f>0) 85 { 86 Edge[i].flow += f; 87 Edge[i ^ 1].flow -= f; 88 flow += f; 89 maxf -= f; 90 if (maxf <= 0) break; 91 if (flow >= needflow) return flow; 92 } 93 } 94 } 95 return flow; 96 } 97 98 int Dicnic_maxflow(int ndflow=INF) 99 {100 int ret = 0;101 needflow = ndflow;102 while (Dicnic_bfs())103 {104 memcpy(tmp_head, Head, sizeof(Head));105 ret += Dicnic_dfs(st, needflow);106 if (ret >= needflow) return ret;107 }108 return ret;109 }110 111 112 }dnc;113 114 int cnt[15][30];115 int main()116 {117 int t;118 scanf("%d", &t);119 int Case = 1;120 while (t--)121 {122 int n,m;123 scanf("%d%d", &n,&m);124 //Bob为1，朋友为2~n,类型为n+1~n+m,汇点为n+m+1125 dnc.Init();126 dnc.set(n + m + 1, 1, n + m + 1);127 memset(cnt, 0, sizeof(cnt));128 for (int i = 1; i <= n; i++)129 {130 int k;131 scanf("%d", &k);132 for (int j = 1; j <= k; j++)133 {134 int v;135 scanf("%d", &v);136 cnt[i][v]++;137 }138 }139 for (int i = 1; i <= m; i++)140 {141 if (cnt[1][i]) dnc.addedge(1, n + i, cnt[1][i]);142 dnc.addedge(n + i, n + m + 1, 1);143 }144 for (int i = 2; i <= n; i++)145 {146 for (int j = 1; j <= m; j++)147 {148 if (cnt[i][j] > 1) dnc.addedge(i, n + j, cnt[i][j] - 1);149 else if (cnt[i][j] == 0) dnc.addedge(n + j, i, 1);150 }151 }152 int flow = dnc.Dicnic_maxflow();153 printf("Case #%d: %d\n",Case++, flow);154 }155 return 0;156 }
View Code

 12、uvalive 3286 Jamie's Contact Groups

　　题意：有n个人，有m个组别，每个人选择一些组别加入，但只能加入其中的一个。问，所有人分组后，人数最多的组别的人数最小是多少？

　　思路：设置源点连向每一个人，权值为1，表示每个人都可以选择加入一个组别；每个人连向其所能加入的组别，权值为1；之后二分最大组别的人数，设其为tmpmax,从每个组别连向汇点，表示最多只能选择tmpmax这么多的人加入，然后求最大流，当==n时看看能不能让tmpmax减少。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 const int maxn = 2100; 10 const int INF = 0x3f3f3f3f; 11 const int maxe = 2 * 1000 + 1000 * 500*2 + 500*2 + 10; 12 struct edge 13 { 14 int from, to, cap, flow, next; 15 edge(int ff=0,int tt=0,int cc=0,int ww=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),next(nn){ } 16 }Edge[maxe]; 17 int Head[maxn], tmp_head[maxn],totedge; 18 19 struct Dicnic 20 { 21 int n, st, ed, needflow; 22 int level[maxn]; 23 int vis[maxn]; 24 25 void Init() 26 { 27 memset(Head, -1, sizeof(Head)); 28 totedge = 0; 29 } 30 31 void set(int nodes, int source, int dest) 32 { 33 n = nodes, st = source, ed = dest; 34 } 35 36 void addedge(int from, int to, int cap) 37 { 38 Edge[totedge] = edge(from, to, cap, 0, Head[from]); 39 Head[from] = totedge++; 40 Edge[totedge] = edge(to, from, 0, 0, Head[to]); 41 Head[to] = totedge++; 42 } 43 44 bool Dicnic_bfs() 45 { 46 memset(level, -1, sizeof(level)); 47 memset(vis, 0, sizeof(vis)); 48 49 queue
             
              q; 50 q.push(st); 51 vis[st] = true; 52 level[st] = 0; 53 while (!q.empty()) 54 { 55 int u = q.front(); 56 q.pop(); 57 58 if (u == ed) return true; 59 for (int i = Head[u]; i != -1; i = Edge[i].next) 60 { 61 int v = Edge[i].to; 62 if (Edge[i].cap > Edge[i].flow && !vis[v]) 63 { 64 vis[v] = true; 65 level[v] = level[u] + 1; 66 q.push(v); 67 } 68 } 69 } 70 return false; 71 } 72 73 int Dicnic_dfs(int u, int maxf) 74 { 75 if (u == ed || maxf == 0) return maxf; 76 77 int flow = 0, f; 78 for (int &i = tmp_head[u]; i != -1; i = Edge[i].next) 79 { 80 if (Edge[i].cap > Edge[i].flow&&level[Edge[i].to] == level[u] + 1) 81 { 82 int f = Dicnic_dfs(Edge[i].to, min(maxf, Edge[i].cap - Edge[i].flow)); 83 if (f > 0) 84 { 85 Edge[i].flow += f; 86 Edge[i ^ 1].flow -= f; 87 flow += f; 88 maxf -= f; 89 if (maxf <= 0) break; 90 } 91 } 92 } 93 return flow; 94 } 95 96 int cal_maxflow() 97 { 98 int ret = 0; 99 while (Dicnic_bfs())100 {101 memcpy(tmp_head, Head, sizeof(Head));102 ret += Dicnic_dfs(st, INF);103 }104 return ret;105 }106 107 void clearflow()108 {109 for (int i = 0; i < totedge; i++) Edge[i].flow = 0;110 }111 }dnc;112 int n, m;113 char name[20];114 string putin;115 int main()116 {117 while (~scanf("%d%d", &n, &m) && n + m)118 {119 dnc.Init();120 //组别为0-m-1,源点为m,人为m+1-m+n,汇点为m+n+1121 dnc.set(n + m + 2, m, m + n + 1);122 for (int i = 1; i <= n; i++)123 {124 dnc.addedge(m, m + i, 1);125 }126 getline(cin, putin);127 for (int i = 1; i <= n; i++)128 {129 getline(cin, putin);130 stringstream ssin(putin);131 ssin >> name;132 int id=0;133 while (ssin>>id)134 {135 dnc.addedge(m + i, id, 1);136 }137 }138 int nowedge =totedge;139 int ans = m;140 int l = 1,r = n;141 while (l<=r)142 {143 dnc.clearflow();144 int curmax = (l + r) / 2;145 if (totedge == nowedge)146 {147 for (int i = 0; i < m; i++)148 {149 dnc.addedge(i, n + m + 1, curmax);150 }151 }152 else153 {154 for (int i = nowedge; i < totedge; i +=2) Edge[i].cap = curmax;155 }156 int tans = dnc.cal_maxflow();157 if (tans == n)158 {159 ans = curmax;160 r = curmax - 1;161 }162 else if (tans < n) l = curmax + 1;163 }164 printf("%d\n", ans);165 }166 return 0;167 }
View Code

 13、uva 11082 Matrix Decompressing

　　题意：有R*C的矩阵，已知前i行元素和前j列元素的和，当矩阵元素在1~20之间时，求满足条件的一个矩阵。

　　思路：因为限制矩阵元素的大小，所以当行连向列时，假设每条边已经至少为1，那么边权可以设为19，然后输出时+1即可。然后从源点连向行i,边权为SUMRi-C;从列连向汇点，边权为SUMCi-R.Dicnic求最大流即可。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 const int maxn = 50;  8 const int maxe = 20 * 2 * 2 + 20 * 20 * 2 + 10;  9 const int INF = 0x3f3f3f3f; 10 struct edge 11 { 12     int from, to, cap, flow, next; 13     edge(int ff=0,int tt=0,int cc=0,int ww=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),next(nn){ } 14 }Edge[maxe]; 15 int Head[maxn], totedge, tmp_head[maxn]; 16  17 struct Dicnic 18 { 19     int n, st, ed; 20     int level[maxn]; 21     int vis[maxn]; 22  23     void Init() 24     { 25         memset(Head, -1, sizeof(Head)); 26         totedge = 0; 27     } 28     void set(int nodes, int source, int dest) 29     { 30         n = nodes, st = source, ed = dest; 31     } 32     void addedge(int from, int to, int cap) 33     { 34         Edge[totedge] = edge(from, to, cap, 0, Head[from]); 35         Head[from] = totedge++; 36         Edge[totedge] = edge(to, from, 0, 0, Head[to]); 37         Head[to] = totedge++; 38     } 39     bool Dicnic_bfs() 40     { 41         memset(level, -1, sizeof(level)); 42         memset(vis, 0, sizeof(vis)); 43  44         queue
           
            q; 45 q.push(st); 46 vis[st] = true; 47 level[st] = 0; 48 while (!q.empty()) 49 { 50 int u = q.front(); 51 q.pop(); 52 if (u == ed) return true; 53 for (int i = Head[u]; i != -1; i = Edge[i].next) 54 { 55 int v = Edge[i].to; 56 if (Edge[i].cap > Edge[i].flow && level[v]==-1&&!vis[v]) 57 { 58 vis[v] = true; 59 level[v] = level[u] + 1; 60 q.push(v); 61 } 62 } 63 } 64 return false; 65 } 66 67 int Dicnic_dfs(int u, int maxf) 68 { 69 if (u == ed || maxf == 0) return maxf; 70 71 int flow = 0, f; 72 for (int&i = tmp_head[u]; i != -1; i = Edge[i].next) 73 { 74 int v = Edge[i].to; 75 if (Edge[i].cap > Edge[i].flow&&level[v] == level[u] + 1) 76 { 77 f = Dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 78 if (f > 0) 79 { 80 Edge[i].flow += f; 81 Edge[i ^ 1].flow -= f; 82 flow += f; 83 maxf -= f; 84 if (maxf == 0) break; 85 } 86 } 87 } 88 return flow; 89 } 90 91 int cal_maxflow() 92 { 93 int ret = 0; 94 while (Dicnic_bfs()) 95 { 96 memcpy(tmp_head, Head, sizeof(Head)); 97 ret += Dicnic_dfs(st, INF); 98 } 99 return ret;100 }101 }dnc;102 int sumr[30], sumc[30];103 int main()104 {105 int t, Case = 1;106 scanf("%d", &t);107 int R, C;108 while (t--)109 {110 scanf("%d%d", &R, &C);111 for (int i = 1; i <= R; i++)112 {113 scanf("%d",&sumr[i]);114 }115 int sum = sumr[R];116 for (int i = R; i>1; i--)117 {118 sumr[i] -= sumr[i - 1];119 }120 for (int i = 1; i <= C; i++)121 {122 scanf("%d", &sumc[i]);123 }124 for (int i = C; i>1; i--)125 {126 sumc[i] -= sumc[i - 1];127 }128 //起点为0，行从1-R，列从R+1-R+C,汇点为R+C+1129 dnc.Init();130 dnc.set(R + C + 2, 0, R + C + 1);131 for (int i = 1; i <= R; i++) dnc.addedge(0, i, sumr[i]-C);132 for (int i = 1; i <= C; i++) dnc.addedge(R + i, R + C + 1, sumc[i]-R);133 int nowedge = totedge;134 for (int i = 1; i <= R; i++)135 {136 for (int j = 1; j <= C; j++)137 {138 dnc.addedge(i, R + j, 19);139 }140 }141 dnc.cal_maxflow();142 nowedge -= 2;143 printf("Matrix %d\n", Case++);144 for (int i = 1; i <=R; i++)145 {146 for (int j = 1; j <= C; j++)147 {148 nowedge += 2;149 printf("%d ", Edge[nowedge].flow + 1);150 }151 printf("\n");152 }153 if(t) printf("\n");154 }155 return 0;156 }
View Code

 14、uvalive 3645 Objective  Berlin

　　题意：有若干座城市，他们之间有n条航线，每条航线的信息包括起始点、终点、起始时间、到达时间、乘客人数。当到达一座城市后，想要乘另一条航线离开至少要过30分钟。问在截止时间前从给定的一个城市前往给定的另一个城市的最大乘客数目。

　　思路：将每条航线i拆成两个点2*i-1和2*i,前者表示从该航线起点站离开，后者表示从该航线终点站到达，前者向后者建边，容量为乘客数目；如果某条航线的起点站为给定的出发城市，则从汇点向其起点站建边，容量为INF；如果某条航线的终点站为给定的前往城市，则从其终点站向汇点建边，容量为INF；如果某条航线到达后至少过30分钟后能够乘另一条航线离开，则前者的终点站向后者的起点站建边，容量为INF。Dicnic求最大流即可。注意建边时航线的到达时间不应该迟于截止时间。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
           5 #include
          
             6 using namespace std;  7 const int maxn = 5000 * 2 + 10;  8 const int maxe = 5000 * 2 + 5000 * 2 + 5000 * 5000 + 5000 * 2 + 5000 * 2 + 100;  9 const int INF = 0x3f3f3f3f; 10 struct edge 11 { 12     int from, to, cap, flow, next; 13     edge(int ff=0,int tt=0,int cc=0,int ww=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),next(nn){ } 14 }Edge[maxe]; 15 int Head[maxn], tmp_head[maxn], totedge; 16 struct dicnic 17 { 18     int n, st, ed; 19     int level[maxn]; 20     bool vis[maxn]; 21  22     void Init() 23     { 24         memset(Head, -1, sizeof(Head)); 25         totedge = 0; 26     } 27     void set(int nodes, int source, int dest) 28     { 29         n = nodes, st = source, ed = dest; 30     } 31     void addedge(int from, int to, int cap) 32     { 33         Edge[totedge] = edge(from, to, cap, 0, Head[from]); 34         Head[from] = totedge++; 35         Edge[totedge] = edge(to, from, 0, 0, Head[to]); 36         Head[to] = totedge++; 37     } 38     bool dicnic_bfs() 39     { 40         memset(level, -1, sizeof(level)); 41         memset(vis, 0, sizeof(vis)); 42         queue
           
            q; 43 q.push(st); 44 vis[st] = true; 45 level[st] = 0; 46 while (!q.empty()) 47 { 48 int u = q.front(); 49 q.pop(); 50 if (u == ed) return true; 51 for (int i = Head[u]; i != -1; i = Edge[i].next) 52 { 53 int v = Edge[i].to; 54 if (Edge[i].cap > Edge[i].flow && !vis[v]) 55 { 56 vis[v] = true; 57 level[v] = level[u] + 1; 58 q.push(v); 59 } 60 } 61 } 62 return false; 63 } 64 65 int dicnic_dfs(int u, int maxf) 66 { 67 if (u == ed || maxf == 0) return maxf; 68 69 int flow = 0, f; 70 for (int &i = tmp_head[u]; i != -1; i = Edge[i].next) 71 { 72 int v = Edge[i].to; 73 if (Edge[i].cap > Edge[i].flow&&level[v] == level[u] + 1) 74 { 75 f = dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 76 if (f > 0) 77 { 78 Edge[i].flow += f; 79 Edge[i ^ 1].flow -= f; 80 flow += f; 81 maxf -= f; 82 if (maxf == 0) break; 83 } 84 } 85 } 86 return flow; 87 } 88 89 int dicnic_maxflow() 90 { 91 int ret = 0; 92 while (dicnic_bfs()) 93 { 94 memcpy(tmp_head, Head, sizeof(Head)); 95 ret += dicnic_dfs(st, INF); 96 } 97 return ret; 98 } 99 }dnc;100 int cities;101 map
            
             mp;102 char name[15];103 char stname[15], edname[15];104 struct fly105 {106 int fromid, toid;107 int cap;108 int sttime, edtime;109 }flight[maxn>>1];110 int main()111 {112 while (~scanf("%d", &cities))113 {114 mp.clear();115 scanf("%s", name);116 mp[name] = 1;117 scanf("%s", name);118 mp[name] = cities;119 int curcityid = 2;120 int edtime, m;121 scanf("%d%d", &edtime, &m);122 dnc.Init();123 dnc.set(m*2 + 2, 0, m*2 + 1);124 for (int i = 1; i <= m; i++)125 {126 scanf("%s%s", stname, edname);127 if (!mp[stname]) mp[stname] = curcityid++;128 if (!mp[edname]) mp[edname] = curcityid++;129 flight[i].fromid = mp[stname], flight[i].toid = mp[edname];130 scanf("%d%d%d", &flight[i].cap, &flight[i].sttime, &flight[i].edtime);131 if (flight[i].fromid == 1) dnc.addedge(0, i * 2 - 1, INF);132 if (flight[i].toid == cities&&flight[i].edtime<=edtime) dnc.addedge(i * 2, m * 2 + 1, INF);133 dnc.addedge(i * 2 - 1, i * 2, flight[i].cap);134 }135 for(int i=1;i<=m;i++)136 {137 if (flight[i].edtime > edtime)continue;138 for (int j = 1; j <=m; j++)139 {140 if (i == j) continue;141 if (flight[i].toid == flight[j].fromid&&(flight[j].sttime/100*60+ flight[j].sttime%100)-(flight[i].edtime/100*60+ flight[i].edtime%100)>=30&&flight[j].edtime<=edtime)142 {143 dnc.addedge(i * 2, j * 2 - 1, INF);144 }145 }146 }147 int ans = dnc.dicnic_maxflow();148 printf("%d\n", ans);149 }150 return 0;151 }
View Code

 15、uvalive 4597/uva 1440 Inspection

　　题意：有一座山上修建了许多滑雪的通道，有n个点构成有向无环图。现在你可以任意从一个起点出发，到达另一个可以到达的点，记为一条路径。求用最少的路径，保证每条边都至少走过一次。

　　思路：有下限的最小流。首先选择出度大于入度的点作为起点，入度大于出度的点作为终点。然后因为每条边可以走多次。那么如果想要走过所有的边，则至多有sum（abs(入度-出度)）条路径。出度大于入度的点连向汇点，源点连向入度大于出度的点，其最大流为可以减少的路径数，并且可以得到每条正向边所要多走的次数（即其flow值）,该值需要累加至入度或出度（表示可以多走）。然后用dfs,当出度-入度>0时，表示能够扩展出一条路径，dfs深搜可以走的点，并且修改入度和出度。这里可以用一个数组记录入度-出度的数值，以方便运算。

参考博客：、、

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 9 10 const int maxn = 210; 11 const int maxe = 100 * 100 * 2 + 100 * 4 + 100; 12 const int INF = 0x3f3f3f3f; 13 int dindgree[maxn], n;//dindgree[i]存的是i结点入度减去出度的值 14 vector
            
             result; 15 struct edge 16 { 17 int from, to, cap, flow, next; 18 edge(int ff=0,int tt=0,int cc=0,int ww=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),next(nn){ } 19 }Edge[maxe]; 20 int Head[maxn], tmp_head[maxn], totedge; 21 struct dicnic 22 { 23 int n, st, ed; 24 int level[maxn]; 25 bool vis[maxn]; 26 27 void Init() 28 { 29 memset(Head, -1, sizeof(Head)); 30 totedge = 0; 31 } 32 void set(int nodes, int source, int dest) 33 { 34 n = nodes, st = source, ed = dest; 35 } 36 void addedge(int from, int to, int cap) 37 { 38 Edge[totedge] = edge(from, to, cap, 0, Head[from]); 39 Head[from] = totedge++; 40 Edge[totedge] = edge(to, from, 0, 0, Head[to]); 41 Head[to] = totedge++; 42 } 43 bool dicnic_bfs() 44 { 45 memset(level, -1, sizeof(level)); 46 memset(vis, 0, sizeof(vis)); 47 queue
             
              q; 48 q.push(st); 49 vis[st] = true; 50 level[st] = 0; 51 while (!q.empty()) 52 { 53 int u = q.front(); 54 q.pop(); 55 if (u == ed) return true; 56 for (int i = Head[u]; i != -1; i = Edge[i].next) 57 { 58 int v = Edge[i].to; 59 if (Edge[i].cap > Edge[i].flow && !vis[v]) 60 { 61 vis[v] = true; 62 level[v] = level[u] + 1; 63 q.push(v); 64 } 65 } 66 } 67 return false; 68 } 69 int dicnic_dfs(int u, int maxf) 70 { 71 if (u == ed || maxf == 0) return maxf; 72 73 int flow = 0, f; 74 for (int &i = tmp_head[u]; i != -1; i = Edge[i].next) 75 { 76 int v = Edge[i].to; 77 if (Edge[i].cap > Edge[i].flow&&level[v] == level[u] + 1) 78 { 79 int f = dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 80 if (f > 0) 81 { 82 Edge[i].flow += f; 83 if(Edge[i].cap>0) dindgree[v] += f;//默认每条边走过一次，流为0.所增加的流表示重复多走过的次数 84 Edge[i ^ 1].flow -= f; 85 flow += f; 86 maxf -= f; 87 if (maxf == 0) break; 88 } 89 } 90 } 91 return flow; 92 } 93 94 int cal_maxflow() 95 { 96 int ret = 0; 97 while (dicnic_bfs()) 98 { 99 memcpy(tmp_head, Head, sizeof(Head));100 ret += dicnic_dfs(st, INF);101 }102 return ret;103 }104 }dnc;105 106 107 108 int main()109 {110 while (~scanf("%d", &n)&&n)111 {112 dnc.Init();113 dnc.set(n + 2, 0, n + 1);114 memset(dindgree, 0, sizeof(dindgree));115 for (int i = 1; i <= n; i++)116 {117 int k;118 scanf("%d", &k);119 dindgree[i] -= k;120 for (int j = 1; j <= k; j++)121 {122 int to;123 scanf("%d", &to);124 dnc.addedge(i, to, INF);//每条边可以走多次，所以容量为INF125 dindgree[to]++;126 }127 }128 int nowedge = totedge;129 int ans = 0;//ans的值就是正向最大流130 for (int i = 1; i <= n; i++)131 {132 /*逆向建边。原本正向应该是源点连向出度大于入度的点，入度大于出度的点连向汇点。133 逆向则是出度大于入度的点连向汇点，源点连向入度大于出度的点。*/134 if (dindgree[i]<0) dnc.addedge(i,n+1, -dindgree[i]),ans+= - dindgree[i];135 if (dindgree[i] >0) dnc.addedge(0,i, dindgree[i]);136 }137 ans -= dnc.cal_maxflow();//减去逆向最大流138 printf("%d\n", ans);139 140 141 for (int i = 1; i <= n; i++)142 {143 while (dindgree[i] < 0)144 { //表示还能将点i作为某一条路线的起点（出度大）145 dindgree[i]++;//修改所还能作为起点的次数146 result.clear();//result记录该条路线147 result.push_back(i);148 int u = i;149 while (1)150 {151 bool ok = false;//表示能否从该点走向其他点152 for (int i = Head[u]; i != -1; i = Edge[i].next)153 {154 ////默认每条边走过一次，流为0.所以如果流为1，表示不能再走这条边。所选择的边应当为正向边，且没有和自设的源点或汇点相连155 if (Edge[i].flow == -1 || Edge[i].cap == 0 || Edge[i].to == n + 1 || Edge[i].to == 0)continue;156 157 ok = true;158 Edge[i].flow--;159 u = Edge[i].to;160 result.push_back(u);161 break;162 }163 if (!ok) break;//不能继续走，退出打印路径164 }165 int sz = result.size();166 for (int i = 0; i < sz; i++)167 {168 if (i) printf(" ");169 printf("%d", result[i]);170 }171 printf("\n");172 }173 }174 }175 return 0;176 }
View Code

 16、uvalive 3487 Duopoly

　　题意：有两家公司分别对拍卖会上的channel进行竞价，分别给出每一组的给出价格和该组所包含的channel（表示用这么多的钱购买该组所有的channel）。但是对于两家公司矛盾的bid,只能选择接受其中一家的竞价，即每一个channel只能被一家公司拥有，求拍卖所得最大利润？

　　思路：如果两家没有矛盾的地方，则最大利润则是格子出价之和。如果有矛盾，则肯定选取利润高的，扔掉代价小的。将有矛盾的两家的bid相连，之后求最大流，最后得到最大流的值为所要扔掉的所有的代价。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std; 10 const int maxn = 6100; 11 const int INF = 0x3f3f3f3f; 12 struct edge 13 { 14 int from, to, cap, flow, next; 15 edge(int ff = 0, int tt = 0, int cc = 0, int ww = 0, int nn = 0) :from(ff), to(tt), cap(cc), flow(ww), next(nn) 16 { 17 } 18 }; 19 vector
              
               Edge; 20 int Head[maxn], tmp_head[maxn], totedge; 21 22 struct dicnic 23 { 24 int n, st, ed; 25 int level[maxn]; 26 bool vis[maxn]; 27 void Init() 28 { 29 memset(Head, -1, sizeof(Head)); 30 totedge = 0; 31 Edge.clear(); 32 } 33 void set(int nodes, int source, int dest) 34 { 35 n = nodes, st = source, ed = dest; 36 } 37 void addedge(int from, int to, int cap) 38 { 39 Edge.push_back(edge(from, to, cap, 0, Head[from])); 40 Head[from] = totedge++; 41 Edge.push_back(edge(to, from, 0, 0, Head[to])); 42 Head[to] = totedge++; 43 } 44 bool dicnic_bfs() 45 { 46 memset(level, -1, sizeof(level)); 47 memset(vis, 0, sizeof(vis)); 48 queue
               
                q; 49 q.push(st); 50 vis[st] = true; 51 level[st] = 0; 52 while (!q.empty()) 53 { 54 int u = q.front(); 55 q.pop(); 56 if (u == ed) return true; 57 for (int i = Head[u]; i != -1; i = Edge[i].next) 58 { 59 int v = Edge[i].to; 60 if (Edge[i].cap > Edge[i].flow && !vis[v]) 61 { 62 vis[v] = true; 63 level[v] = level[u] + 1; 64 q.push(v); 65 } 66 } 67 } 68 return false; 69 } 70 71 int dicnic_dfs(int u, int maxf) 72 { 73 if (u == ed || maxf == 0) return maxf; 74 75 int flow = 0, f; 76 for (int &i = tmp_head[u]; i != -1; i = Edge[i].next) 77 { 78 int v = Edge[i].to; 79 if (Edge[i].cap > Edge[i].flow&&level[v] == level[u] + 1) 80 { 81 f = dicnic_dfs(v, min(maxf, Edge[i].cap - Edge[i].flow)); 82 if (f > 0) 83 { 84 Edge[i].flow += f; 85 Edge[i ^ 1].flow -= f; 86 flow += f; 87 maxf -= f; 88 if (maxf == 0) break; 89 } 90 } 91 } 92 return flow; 93 } 94 int cal_maxflow() 95 { 96 int ret = 0; 97 while (dicnic_bfs()) 98 { 99 memcpy(tmp_head, Head, sizeof(Head));100 ret += dicnic_dfs(st, INF);101 }102 return ret;103 }104 }dnc;105 int visa[300010];106 bool visp[3100][3100];107 int main()108 {109 int t;110 scanf("%d", &t);111 int Case = 1;112 while (t--)113 {114 dnc.Init();115 int na, nb;116 memset(visa, 0, sizeof(visa));117 memset(visp, 0, sizeof(visp));118 string tmp;119 int price, chnl;120 int sum = 0;121 122 scanf("%d", &na);123 getline(cin, tmp);124 for (int i = 1; i <= na; i++)125 {126 getline(cin, tmp);127 stringstream ssin(tmp);128 ssin >> price;129 sum += price;130 while (ssin >> chnl)131 {132 visa[chnl] = i;133 }134 dnc.addedge(0, i, price);135 }136 scanf("%d", &nb);137 getline(cin, tmp);138 for (int i = na + 1; i <= na + nb; i++)139 {140 getline(cin, tmp);141 stringstream ssin(tmp);142 ssin >> price;143 sum += price;144 while (ssin >> chnl)145 {146 if (visa[chnl] && !visp[visa[chnl]][i - na])147 {148 dnc.addedge(visa[chnl], i, INF);149 visp[visa[chnl]][i - na] = true;150 }151 }152 dnc.addedge(i, na + nb + 1, price);153 }154 dnc.set(na + nb + 2, 0, na + nb + 1);155 int ans = dnc.cal_maxflow();//所有矛盾的bid组数中代价的最小值156 printf("Case %d:\n", Case++);157 printf("%d\n", sum - ans);158 if (t) printf("\n");159 }160 return 0;161 }
View Code

 

 

转载于:https://www.cnblogs.com/ivan-count/p/7348492.html

你可能感兴趣的文章
SQL Server---存储过程
查看>>
MySQL Performance-Schema(二) 理论篇
查看>>
搭建SSH详细步骤及相关说明
查看>>
Android IOS WebRTC 音视频开发总结（五五）-- 音视频通讯中的抗丢包与带宽自适应原理...
查看>>
Libgdx: 将Texturepacker打包的PNG图片还原成一张一张的单个的
查看>>
再议Swift操作符重载
查看>>
pc机进入android的shell
查看>>
javascript Date format(js日期格式化)
查看>>
Loadrunner中参数化实战（6）-Random+Each occurrence
查看>>
tomcatserver解析（六）-- Acceptor
查看>>
asp.net判断访问者是否来自移动端
查看>>
Python 一些常用模块的安装
查看>>
严苛模式（StrictMode）
查看>>
牛客网-《剑指offer》-跳台阶
查看>>
unity, editorWindow update计时
查看>>
我的VSTO之路(二)：VSTO程序基本知识
查看>>
DataTable.Compute 性能慢的问题
查看>>
分层是一种思想
查看>>
Prime Ring Problem
查看>>
Windows系统bug
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-29 07:53:35   当前IP: 3.147.127.96   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我