Students(判断二分图+最大匹配)(匈牙利模板)

1、poj 2195 Going
Home(二分图最小权匹配)

1、hdu 2444 The Accomodation of
Students(判断二分图+最大匹配)(匈牙利模板)

  题意:图上有n个房子,n个人,现在布局每个人重回一所房间,求最小的步数和。

  题意:一共有n个学生,m对关系:A认识B。问能不能将持有的人分为两批,每批之间的人都相互认识,要是得以,输出每批的人头。即判断是还是不是为二分图,以及求二分图的最大匹配。

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

  思路:判断是还是不是为二分图(DFS或BFS);求二分图的最大匹配:匈牙利算法。

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

图片 1图片 2

    http://blog.sina.com.cn/s/blog\_691ce2b701016reh.html

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 int n,m;
 5 const int maxn = 210;//x集合和y集合总最大的点数
 6 bool mp[maxn][maxn];//1表示该ij可以匹配
 7 int cx[maxn];//记录x集合中匹配的y元素是哪一个
 8 int cy[maxn];//记录y集合中匹配的x元素是哪一个
 9 int vis[maxn];//标记该顶点是否访问过
10 int cntx;
11 bool dfs(int u)
12 {
13     for (int v = 1; v <= n; v++)//两个集合内共有n个元素
14     {
15         if (mp[u][v] && !vis[v])
16         {
17             vis[v] = 1;
18             if (cy[v] == -1 || dfs(cy[v]))//)//如果y集合中的v元素没有匹配或者是v已经匹配,但是从cy[v]中能够找到一条增广路
19             {
20                 cx[u] = v; cy[v] = u;
21                 return 1;
22             }
23         }
24     }
25     return 0;
26 }
27 int maxmatch()//匈牙利算法主函数
28 {
29     int ans = 0;
30     memset(cx, 0xff, sizeof cx);//初始值为-1表示两个集合中都没有匹配的元素!
31     memset(cy, 0xff, sizeof cy);
32     for (int i = 1; i <= n; i++)
33         if (cx[i] == -1)//如果i未匹配
34         {
35             memset(vis, 0, sizeof(vis));
36             ans += dfs(i);
37         }
38     return ans/2;//对两个部里的都匹配了,这样就相当于匹配了两次了  
39 }
40 bool istwo()
41 {//判断是否为二分图
42     queue<int>q;
43     memset(vis, 0, sizeof(vis));
44     q.push(1);
45     vis[1] = true;
46     while (!q.empty())
47     {
48         int u = q.front();
49         q.pop();
50         for (int i = 1; i <= n; i++)
51         {
52             if (mp[u][i])
53             {
54                 if (vis[i] == 0)
55                 {
56                     if (vis[u] == 1) vis[i] = 2;
57                     else vis[i] = 1;
58                     q.push(i);
59                 }
60                 else
61                 {
62                     if (vis[i] == vis[u]) return false;
63                 }
64             }
65         }
66     }
67     return true;
68 }
69 int main()
70 {
71     while (~scanf("%d%d", &n, &m))
72     {
73         memset(mp ,0, sizeof(mp));
74         while (m--)
75         {
76             int a, b;
77             scanf("%d%d", &a, &b);
78             mp[a][b] = mp[b][a] = 1;
79         }
80         if (!istwo()|| n == 1)
81         {
82             printf("No\n");
83         }
84         else
85         {
86             int ans = maxmatch();
87             printf("%d\n", ans);
88         }
89     }
90 
91     return 0;
92 }

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

View Code

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

2、hdu 1083 Courses(最大匹配)

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

  题意:有P种课程,N个学生。接下来P行,第i行第四个Ni表示喜欢第i个学科的学员的人口,接下去是Ni个学生。问:能不能有一种匹配使得各类学员都选一门分裂的学科,同时拥有科目都出现。

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

  思路:二分图最大匹配,匈牙利算法,课程为x集,学生为y集。判断最大匹配数是或不是为P。

图片 3图片 4

图片 5图片 6

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  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 }
 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 using namespace std;
 5 int n, p;
 6 const int maxn = 310;//最大学生数
 7 const int maxp = 110;//最大学科数
 8 bool mp[maxp][maxn];//1表示该ij可以匹配
 9 int cx[maxp];//记录x集合中匹配的y元素是哪一个
10 int cy[maxn];//记录y集合中匹配的x元素是哪一个
11 int vis[maxn];//标记该顶点是否访问过
12 bool dfs(int u)
13 {
14     for (int v = 1; v <= n; v++)
15     {
16         if (mp[u][v] && !vis[v])
17         {
18             vis[v] = 1;
19             if (cy[v] == -1 || dfs(cy[v]))//)//如果y集合中的v元素没有匹配或者是v已经匹配,但是从cy[v]中能够找到一条增广路
20             {
21                 cx[u] = v; cy[v] = u;
22                 return 1;
23             }
24         }
25     }
26     return 0;
27 }
28 int maxmatch()//匈牙利算法主函数
29 {
30     int ans = 0;
31     memset(cx, 0xff, sizeof cx);//初始值为-1表示两个集合中都没有匹配的元素!
32     memset(cy, 0xff, sizeof cy);
33     for (int i = 1; i <= p; i++)
34         if (cx[i] == -1)//如果i未匹配
35         {
36             memset(vis, 0, sizeof(vis));
37             ans += dfs(i);
38         }
39     return ans;
40 }
41 
42 int main()
43 {
44     int t;
45     scanf("%d", &t);
46     while (t--)
47     {
48         scanf("%d%d", &p, &n);
49         memset(mp, 0, sizeof(mp));
50         for (int i = 1; i <= p; i++)
51         {
52             int count;
53             scanf("%d", &count);
54             for (int j = 1; j <= count; j++)
55             {
56                 int v;
57                 scanf("%d", &v);
58                 mp[i][v] = true;
59             }
60        }
61         int ans = maxmatch();
62         if (ans < p)printf("NO\n");
63         else printf("YES\n");
64     }
65 
66     return 0;
67 }

View Code

View Code

 2、uva 11383 Golden Tiger Claw

3、hdu 1281 棋盘游戏(最大匹配)

  题意:n*n的矩阵,现在亟需确定row和col数组,保障在w(i,j)<=row(i)+col(j)的意况下,求row数组和col数组的和的蝇头值。

  题意:所有棋子无法同行或同列。给出棋子能够放的义务,问最多能放多少个,同时提交紧要点(去掉某个地点后就不能够有限支撑放尽量多的棋子)的个数。

  思路:二分图完美包容,KM算法。

  思路:x集代表行,y集代表列,对于可以放的职位(x,y)将x和y连一条边。最多能放的棋子即该二分图的最大匹配。接下来每便去掉一个职分看看最大匹配是不是不变,假使改变则为主要点。

图片 7图片 8

图片 9图片 10

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  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 }
 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 using namespace std;
 5 int n, m, k;
 6 const int maxr = 110;//最大行数
 7 const int maxc = 110;//最大列数
 8 const int maxk = 10010;//最多可放位置
 9 bool mp[maxr][maxc];//1表示该ij可以匹配
10 int cx[maxc];//记录x集合中匹配的y元素是哪一个
11 int cy[maxr];//记录y集合中匹配的x元素是哪一个
12 int vis[maxr];//标记该顶点是否访问过
13 struct point
14 {
15     int x;
16     int y;
17 }points[maxk];
18 bool dfs(int u)
19 {
20     for (int v = 1; v <= m; v++)
21     {
22         if (mp[u][v] && !vis[v])
23         {
24             vis[v] = 1;
25             if (cy[v] == -1 || dfs(cy[v]))//)//如果y集合中的v元素没有匹配或者是v已经匹配,但是从cy[v]中能够找到一条增广路
26             {
27                 cx[u] = v; cy[v] = u;
28                 return 1;
29             }
30         }
31     }
32     return 0;
33 }
34 int maxmatch()//匈牙利算法主函数
35 {
36     int ans = 0;
37     memset(cx, 0xff, sizeof cx);//初始值为-1表示两个集合中都没有匹配的元素!
38     memset(cy, 0xff, sizeof cy);
39     for (int i = 1; i <= n; i++)
40         if (cx[i] == -1)//如果i未匹配
41         {
42             memset(vis, 0, sizeof(vis));
43             ans += dfs(i);
44         }
45     return ans;
46 }
47 
48 int main()
49 {
50     int Case = 1;
51     while (~scanf("%d%d%d", &n, &m, &k))
52     {
53         memset(mp, 0, sizeof(mp));
54         for (int i = 1; i <= k; i++)
55         {
56             scanf("%d%d", &points[i].x, &points[i].y);
57             mp[points[i].x][points[i].y] = 1;
58         }
59         int ans = maxmatch();
60         int import = 0;
61         for (int i = 1; i <= k; i++)
62         {
63             mp[points[i].x][points[i].y] = 0;
64             int tmp = maxmatch();
65             mp[points[i].x][points[i].y] = 1;
66             if (tmp < ans) import++;
67         }
68         printf("Board %d have %d important blanks for %d chessmen.\n", Case++, import, ans);
69     }
70 
71     return 0;
72 }

View Code

View Code

 3、uvalive 2238 Fixed Partition Memory
Management

4、HDU 2819 Swap(最大匹配)

  题意:有m个内存,n个程序,每个程序对应分歧的内存大小有两样的运作时刻。该程序对应已知的内存单元的时间为对应的取下线最相近的时刻。求所有程序的统计束时间的平均值最小。

  题意:给出n*n的矩阵,问是或不是通过置换某两行或某两列若干次后,使得其对角线上元素均为1.

  思路:对于在一个内存中的景象:设该内存中有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算法。

  思路:只调换行或只互换列均可直达同等的效益(如若达不到,表达无解)。列既作为x集,也当作y集,[i][j]连线表示将第j列和第i列沟通(当[x][y]为1时,将[x][y]连线,表示将可以其换到[x][x])。然后求此二分图的最大匹配。输出每个匹配时,注意调换,否则会多输出。匈牙利算法。

图片 11图片 12

图片 13图片 14

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  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                 else
128                 {
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*tmp
138                     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 }
 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 #include<algorithm>
 5 using namespace std;
 6 int n;
 7 const int maxr = 110;//最大行数
 8 const int maxc = 110;//最大列数
 9 const int maxk = 1010;//最多可放位置
10 bool mp[maxr][maxc];//1表示该ij可以匹配
11 int cx[maxc];//记录x集合中匹配的y元素是哪一个
12 int cy[maxr];//记录y集合中匹配的x元素是哪一个
13 int vis[maxr];//标记该顶点是否访问过
14 struct stp
15 {
16     int x;
17     int y;
18 }stps[maxk];
19 bool dfs(int u)
20 {
21     for (int v = 1; v <= n; v++)
22     {
23         if (mp[u][v] && !vis[v])
24         {
25             vis[v] = 1;
26             if (cy[v] == -1 || dfs(cy[v]))//)//如果y集合中的v元素没有匹配或者是v已经匹配,但是从cy[v]中能够找到一条增广路
27             {
28                 cx[u] = v; cy[v] = u;
29                 return 1;
30             }
31         }
32     }
33     return 0;
34 }
35 int maxmatch()//匈牙利算法主函数
36 {
37     int ans = 0;
38     memset(cx, 0xff, sizeof cx);//初始值为-1表示两个集合中都没有匹配的元素!
39     memset(cy, 0xff, sizeof cy);
40     for (int i = 1; i <= n; i++)
41         if (cx[i] == -1)//如果i未匹配
42         {
43             memset(vis, 0, sizeof(vis));
44             ans += dfs(i);
45         }
46     return ans;
47 }
48 
49 int main()
50 {
51     while (~scanf("%d", &n))
52     {
53         memset(mp, 0, sizeof(mp));
54         for (int i = 1; i <= n; i++)
55         {
56             for (int j = 1; j <= n; j++)
57             {
58                 int v;
59                 scanf("%d", &v);
60                 if (v > 0) mp[i][j] = 1;
61             }
62         }
63         int ans = maxmatch();
64         if (ans < n)printf("-1\n");
65         else
66         {
67             int t = 0;
68             for (int i = 1; i <= n; i++)
69             {
70                 int j;
71                 for (j = 1; j <= n; j++) if (cy[j] == i)break;
72                 if (i != j)
73                 {
74                     stps[t].x = i, stps[t].y = j;
75                     t++;
76                     swap(cy[i], cy[j]);
77                 }
78             }
79             printf("%d\n", t);
80             for (int i = 0; i < t; i++)
81             {
82                 printf("C %d %d\n", stps[i].x, stps[i].y);
83             }
84         }
85     }
86 
87     return 0;
88 }

View Code

View Code

 4、uvalive 3989 Ladies’ Choice

5、hdu 2389 Rain on your
Parade(最大匹配)(Hopcroft-Carp算法模板)

  题意:有n个女孩,n个男孩,现在亟待同盟出n对男孩和女孩。对于每个女孩,按照喜欢程度有降序的男生order,对于男生也一如既往。现在要求以女子优先,有限支撑在能合营全体的情形下,每个女孩子的选料都是最好的。

  题意:有m个人,t时刻后会下雨。地上有n把伞,每把伞只好一个人用。给出人和伞的坐标,以及人的速度,问在降雨前,最多能有稍许个人获得伞?

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

  思路:人作为x集,伞作为y集,假诺人可以到达伞的职位,把该人的号码和该伞的号子连线。之后求最大匹配。Hopcroft-Carp算法。

图片 15图片 16

图片 17图片 18

 1 //稳定婚姻问题
 2 
 3 #include<iostream>
 4 #include<queue>
 5 #include<cstdio>
 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<int>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 }
  1 #include<iostream>
  2 #include<queue>
  3 #include<memory.h>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 int n,t,m,Nx,Ny,dis;
  8 const int maxn = 3100;//最大行数
  9 const int maxm = 3100;//最大列数
 10 const int maxk = 3100;
 11 const int INF = 0x7fffffff;
 12 bool mp[maxn][maxm];//1表示该ij可以匹配
 13 int cx[maxm];//记录x集合中匹配的y元素是哪一个
 14 int dx[maxm];
 15 int cy[maxn];//记录y集合中匹配的x元素是哪一个
 16 int dy[maxn];
 17 int vis[maxm];//标记该顶点是否访问过
 18 struct point
 19 {
 20     int x;
 21     int y;
 22     int v;
 23 }customer[maxk];
 24 struct point2
 25 {
 26     int x;
 27     int y;
 28 }unbrella[maxk];
 29 bool searchP(void)    //BFS   
 30 {
 31     queue <int> Q;
 32     dis = INF;
 33     memset(dx, -1, sizeof(dx));
 34     memset(dy, -1, sizeof(dy));
 35     for (int i = 1; i <= Nx; i++)
 36         if (cx[i] == -1)
 37         {
 38             Q.push(i); dx[i] = 0;
 39         }
 40     while (!Q.empty())
 41     {
 42         int u = Q.front(); Q.pop();
 43         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
 44         for (int v = 1; v <= Ny; v++)
 45             if (mp[u][v] && dy[v] == -1)
 46             {        //v是未匹配点  
 47                 dy[v] = dx[u] + 1;
 48                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
 49                 else
 50                 {
 51                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
 52                     Q.push(cy[v]);
 53                 }
 54             }
 55     }
 56     return dis != INF;
 57 }
 58 
 59 bool DFS(int u)
 60 {
 61     for (int v = 1; v <= Ny; v++)
 62         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
 63         {
 64             vis[v] = 1;
 65             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
 66             if (cy[v] == -1 || DFS(cy[v]))
 67             {     //是增广路径,更新匹配集  
 68                 cy[v] = u; cx[u] = v;
 69                 return 1;
 70             }
 71         }
 72     return 0;
 73 }
 74 
 75 int MaxMatch(void)
 76 {
 77     int res = 0;
 78     memset(cx, -1, sizeof(cx));
 79     memset(cy, -1, sizeof(cy));
 80     while (searchP())
 81     {
 82         memset(vis, 0, sizeof(vis));
 83         for (int i = 1; i <= Nx; i++)
 84             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
 85     }
 86     return res;
 87 }
 88 
 89 int main()
 90 {
 91     int C;
 92     scanf("%d", &C);
 93     int Case = 1;
 94     while (C--)
 95     {
 96         scanf("%d", &t);
 97         memset(mp, 0, sizeof(mp));
 98         scanf("%d", &m);
 99         for (int i = 1; i <= m; i++)
100         {
101             scanf("%d%d%d", &customer[i].x, &customer[i].y, &customer[i].v);
102         }
103         scanf("%d", &n);
104         for (int i = 1; i <= n; i++)
105         {
106             scanf("%d%d", &unbrella[i].x, &unbrella[i].y);
107         }
108         for (int i = 1; i <= n; i++)
109         {
110             for (int j = 1; j <= m; j++)
111             {
112                 double dis = sqrt((unbrella[i].x - customer[j].x)*(unbrella[i].x - customer[j].x) + (unbrella[i].y - customer[j].y)*(unbrella[i].y - customer[j].y));
113                 if (dis <= t*customer[j].v) mp[i][j] = true;
114             }
115         }
116         Nx = n, Ny = m;
117         int ans = MaxMatch();
118         printf("Scenario #%d:\n", Case++);
119         printf("%d\n\n", ans);
120     }
121     return 0;
122 }

View Code

View Code

 5、uva 11419 SAM I AM

6、hdu 4185 Oil Skimming

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

  题意:给出一张图,每相邻多个油田能够创造一起沟渠。问最大渠道的数码。

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

  思路:给每一个油田编号。油田既作为x集,又作为y集,即使两块油田相邻,则连线。之后求最大匹配。

图片 19图片 20

图片 21图片 22

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 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 }
  1 #include<iostream>
  2 #include<queue>
  3 #include<memory.h>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 int n, t, m, Nx, Ny, dis;
  8 const int maxn = 650;//最大行数
  9 const int maxm = 650;//最大列数
 10 const int maxk = 360005;
 11 const int INF = 0x7fffffff;
 12 char M[maxn][maxm];
 13 bool mp[maxn][maxn];//1表示该ij可以匹配
 14 int cx[maxk];//记录x集合中匹配的y元素是哪一个
 15 int dx[maxk];
 16 int cy[maxk];//记录y集合中匹配的x元素是哪一个
 17 int dy[maxk];
 18 int vis[maxk];//标记该顶点是否访问过
 19 struct point
 20 {
 21     int x;
 22     int y;
 23 }oils[maxk];
 24 bool searchP(void)    //BFS   
 25 {
 26     queue <int> Q;
 27     dis = INF;
 28     memset(dx, -1, sizeof(dx));
 29     memset(dy, -1, sizeof(dy));
 30     for (int i = 1; i <= Nx; i++)
 31         if (cx[i] == -1)
 32         {
 33             Q.push(i); dx[i] = 0;
 34         }
 35     while (!Q.empty())
 36     {
 37         int u = Q.front(); Q.pop();
 38         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
 39         for (int v = 1; v <= Ny; v++)
 40             if (mp[u][v] && dy[v] == -1)
 41             {        //v是未匹配点  
 42                 dy[v] = dx[u] + 1;
 43                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
 44                 else
 45                 {
 46                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
 47                     Q.push(cy[v]);
 48                 }
 49             }
 50     }
 51     return dis != INF;
 52 }
 53 
 54 bool DFS(int u)
 55 {
 56     for (int v = 1; v <= Ny; v++)
 57         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
 58         {
 59             vis[v] = 1;
 60             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
 61             if (cy[v] == -1 || DFS(cy[v]))
 62             {     //是增广路径,更新匹配集  
 63                 cy[v] = u; cx[u] = v;
 64                 return 1;
 65             }
 66         }
 67     return 0;
 68 }
 69 
 70 int MaxMatch(void)
 71 {
 72     int res = 0;
 73     memset(cx, -1, sizeof(cx));
 74     memset(cy, -1, sizeof(cy));
 75     while (searchP())
 76     {
 77         memset(vis, 0, sizeof(vis));
 78         for (int i = 1; i <= Nx; i++)
 79             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
 80     }
 81     return res;
 82 }
 83 
 84 int main()
 85 {
 86     int C,N;
 87     scanf("%d", &C);
 88     int Case = 1;
 89     while (C--)
 90     {
 91         scanf("%d", &N);
 92         memset(mp, 0, sizeof(mp));
 93         int cnt = 0;
 94         for (int i = 1; i <= N; i++)
 95         {
 96             for (int j = 1; j <= N; j++)
 97             {
 98                 cin >> M[i][j];
 99                 if (M[i][j] == '#')
100                 {
101                     oils[cnt].x = i;
102                     oils[cnt].y = j;
103                     cnt++;
104                 }
105             }
106         }
107         for (int i = 0; i < cnt; i++)
108         {
109             for (int j = 0; j < cnt; j++)
110             {
111                 if (abs(oils[i].x - oils[j].x) + abs(oils[i].y - oils[j].y) == 1)
112                 {
113                     mp[i+1][j+1] = 1;
114                 }
115             }
116         }
117         Nx = cnt, Ny = cnt;
118         int ans = MaxMatch();
119         printf("Case %d: %d\n", Case++,ans/2);
120     }
121     return 0;
122 }

View Code

View Code

 6、uvalive 3415 Guardian of
Decency

7、poj 3020 Antenna
Placement(无向二分图的小小路径覆盖)

  题意:借使多人里面身高差大于40要么同一性别或者喜欢分化的音乐依旧喜欢同一的移位,则那六人得以同时带去出游。问当带出的所有人两两之间起码满意其中一个规则下,所能带走的最多的人?

  题意:每个天线最多只好覆盖自己所在的格子和一个紧邻的职位(可以是都市也可以是空地)。问最少的天线数目。

  思路:倘若五人4个标准化都不合乎,那么一定不能而且指引。现在亟须要能带走的最多,则需求最小化不可能指引的。当4个规范都不吻合时,五人建边,求所选的人两两里头不可以连边,即最大独立集问题(选拔尽量多的结点,使得任意一条边的八个端点不会同时被入选)。

  思路:把每个城市拆成两点,让其既属于x集又属于y集,然后把相邻的城市连线。总结最大匹配,然后用总城市数-最大匹配数即得最小路径覆盖(用最少的边,覆盖所有终端。每个终端开始各有一条边,假若五个点不断,则为了使答案中的每条边都不可以交于相同一点,所以要减1.尾声即减去最大匹配数).

图片 23图片 24

图片 25图片 26

  1 #include<iostream>
  2 #include<map>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 using namespace std;
  8 const int maxn = 510;
  9 map<string, int>music;
 10 map<string, int>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 }
  1 #include<iostream>
  2 #include<queue>
  3 #include<memory.h>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 int n, t, m, Nx, Ny, dis,totalr,totalc;
  8 const int maxn = 50;//最大行数
  9 const int maxm = 15;//最大列数
 10 const int maxk = 1000;
 11 const int INF = 0x7fffffff;
 12 int M[maxn][maxm];
 13 bool mp[maxk][maxk];//1表示该ij可以匹配
 14 int cx[maxk];//记录x集合中匹配的y元素是哪一个
 15 int dx[maxk];
 16 int cy[maxk];//记录y集合中匹配的x元素是哪一个
 17 int dy[maxk];
 18 int vis[maxk];//标记该顶点是否访问过
 19 int dr[] = { 0,0,1,-1 };
 20 int dc[] = { 1,-1,0,0 };
 21 struct point
 22 {
 23     int x;
 24     int y;
 25 }oils[maxk];
 26 bool searchP(void)    //BFS   
 27 {
 28     queue <int> Q;
 29     dis = INF;
 30     memset(dx, -1, sizeof(dx));
 31     memset(dy, -1, sizeof(dy));
 32     for (int i = 1; i <= Nx; i++)
 33         if (cx[i] == -1)
 34         {
 35             Q.push(i); dx[i] = 0;
 36         }
 37     while (!Q.empty())
 38     {
 39         int u = Q.front(); Q.pop();
 40         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
 41         for (int v = 1; v <= Ny; v++)
 42             if (mp[u][v] && dy[v] == -1)
 43             {        //v是未匹配点  
 44                 dy[v] = dx[u] + 1;
 45                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
 46                 else
 47                 {
 48                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
 49                     Q.push(cy[v]);
 50                 }
 51             }
 52     }
 53     return dis != INF;
 54 }
 55 
 56 bool DFS(int u)
 57 {
 58     for (int v = 1; v <= Ny; v++)
 59         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
 60         {
 61             vis[v] = 1;
 62             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
 63             if (cy[v] == -1 || DFS(cy[v]))
 64             {     //是增广路径,更新匹配集  
 65                 cy[v] = u; cx[u] = v;
 66                 return 1;
 67             }
 68         }
 69     return 0;
 70 }
 71 
 72 int MaxMatch()
 73 {
 74     int res = 0;
 75     memset(cx, -1, sizeof(cx));
 76     memset(cy, -1, sizeof(cy));
 77     while (searchP())
 78     {
 79         memset(vis, 0, sizeof(vis));
 80         for (int i = 1; i <= Nx; i++)
 81             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
 82     }
 83     return res;
 84 }
 85 
 86 int main()
 87 {
 88     int C, N;
 89     scanf("%d", &C);
 90     int Case = 1;
 91     while (C--)
 92     {
 93         scanf("%d%d", &totalr,&totalc);
 94         memset(mp, 0, sizeof(mp));
 95         int cnt = 0;
 96         for (int i = 1; i <= totalr; i++)
 97         {
 98             for (int j = 1; j <= totalc; j++)
 99             {
100                 char c;
101                 cin >> c;
102                 if (c == 'o')
103                 {
104                     M[i][j] = 0;
105                 }
106                 else
107                 {
108                     M[i][j] = ++cnt;
109                 }
110             }
111         }
112         // //通过“拆点”操作,把每一个城市拆分为2个,分别属于所构造的二分图的两个点集  
113         for (int i = 1; i <= totalr; i++)
114         {
115             for (int j = 1; j <= totalc; j++)
116             {
117                 if (M[i][j] > 0)
118                 {
119                     int u = M[i][j];
120                     for (int k = 0; k < 4; k++)
121                     {
122                         int tr = i + dr[k];
123                         int tc = j + dc[k];
124                         if (tr >= 1 && tr <= totalr&&tc >= 1 && tc <= totalc)
125                         {
126                             if (M[tr][tc] > 0)
127                             {
128                                 mp[u][M[tr][tc]] = true;
129                             }
130                         }
131                     }
132                 }
133             }
134         }
135 
136         Nx = cnt, Ny = cnt;
137         int ans = MaxMatch();
138         printf("%d\n", cnt-ans / 2);//无向二分图:最小路径覆盖数 = "拆点"前原图的顶点数 - 最大匹配数/2  
139     }
140     return 0;
141 }

View Code

View Code

 7、uvalive 3126 Taxi Cab Scheme

8、hdu 1054 Strategic Game POJ1463

  题意:有n个预定,记录其约定出租车的日子、开首地点、终点地点,并且一辆出租同时只好接送一个预定的游客。问最少须求有些出租车?

  题意:有一棵树,现在内需在树上结点的任务放士兵,每个士兵可以防守与其所在顶点相连接的边。问最少放多少士兵,可以防守所有的边。

  思路:若是一辆出租车从第i个约定甘休后能赶到第j个约定的地址,且至少可以提前1分钟到,则两点连线。整个问题为有向无环图的微小路径覆盖问题。

  思路:每个点既属于x集,又属于y集,两点时期若有边则连线。总计最大匹配。(要是a和b、c、d相连,那么只要选拔a和b相连的那条边,则不可以再选a点,也就不能再选和a连接的边)

小小路径覆盖参考:http://blog.csdn.net/qq_37321281/article/details/77839207

图片 27图片 28

图片 29图片 30

  1 #include<iostream>
  2 #include<queue>
  3 #include<memory.h>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 int n, t, m, Nx, Ny, dis, totalr, totalc;
  8 const int maxn = 50;//最大行数
  9 const int maxm = 15;//最大列数
 10 const int maxk = 1505;
 11 const int INF = 0x7fffffff;
 12 bool mp[maxk][maxk];//1表示该ij可以匹配
 13 int cx[maxk];//记录x集合中匹配的y元素是哪一个
 14 int dx[maxk];
 15 int cy[maxk];//记录y集合中匹配的x元素是哪一个
 16 int dy[maxk];
 17 int vis[maxk];//标记该顶点是否访问过
 18 bool searchP(void)    //BFS   
 19 {
 20     queue <int> Q;
 21     dis = INF;
 22     memset(dx, -1, sizeof(dx));
 23     memset(dy, -1, sizeof(dy));
 24     for (int i = 1; i <= Nx; i++)
 25         if (cx[i] == -1)
 26         {
 27             Q.push(i); dx[i] = 0;
 28         }
 29     while (!Q.empty())
 30     {
 31         int u = Q.front(); Q.pop();
 32         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
 33         for (int v = 1; v <= Ny; v++)
 34             if (mp[u][v] && dy[v] == -1)
 35             {        //v是未匹配点  
 36                 dy[v] = dx[u] + 1;
 37                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
 38                 else
 39                 {
 40                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
 41                     Q.push(cy[v]);
 42                 }
 43             }
 44     }
 45     return dis != INF;
 46 }
 47 
 48 bool DFS(int u)
 49 {
 50     for (int v = 1; v <= Ny; v++)
 51         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
 52         {
 53             vis[v] = 1;
 54             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
 55             if (cy[v] == -1 || DFS(cy[v]))
 56             {     //是增广路径,更新匹配集  
 57                 cy[v] = u; cx[u] = v;
 58                 return 1;
 59             }
 60         }
 61     return 0;
 62 }
 63 
 64 int MaxMatch()
 65 {
 66     int res = 0;
 67     memset(cx, -1, sizeof(cx));
 68     memset(cy, -1, sizeof(cy));
 69     while (searchP())
 70     {
 71         memset(vis, 0, sizeof(vis));
 72         for (int i = 1; i <= Nx; i++)
 73             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
 74     }
 75     return res;
 76 }
 77 
 78 int main()
 79 {
 80     while (~scanf("%d",&n))
 81     {
 82         memset(mp, 0, sizeof(mp));
 83         int cnt = 0,cur,num;
 84         char c;
 85         for (int i = 1; i <= n; i++)
 86         {
 87             cin >> cur >> c >> c >> num >> c;
 88             cur = cur + 1;
 89             for (int j = 1; j <= num; j++)
 90             {
 91                 int v;
 92                 cin >> v;
 93                 v = v + 1;
 94                 mp[cur][v] = true;
 95                 mp[v][cur] = true;
 96             }
 97         }
 98         
 99 
100         Nx = n, Ny = n;
101         int ans = MaxMatch();
102         printf("%d\n", ans / 2);
103     }
104     return 0;
105 }
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 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 node
45 {
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

View Code

9、hdu 1151/poj 1422 Air Raid

 8、uva 11248 Frequency Hopping

  题意:有一有向无环图,倘若在一个结点放士兵,那么其也可以防守与其相连的有向边能抵达的结点。问最少要求有些守卫可以防守所有结点。

  题意:有n个基站,用有向边相连,问是还是不是足以从1到N有流量至少为C的最大流?没有的话,是或不是可以附加一条边的容量而达标目标?

  思路:同上一题,不过注意有向边。

  思路:dicnic求最大流。增大的边肯定拔取最小割中的边。在那事后,从求完最大流后的残存网络求其是还是不是知足条件。

图片 31图片 32

 

 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 int n, t, m, Nx, Ny, dis, totalr, totalc;
 8 const int maxn = 50;//最大行数
 9 const int maxm = 15;//最大列数
10 const int maxk = 125;//x集与y集最多元素
11 const int INF = 0x7fffffff;
12 bool mp[maxk][maxk];//1表示该ij可以匹配
13 int cx[maxk];//记录x集合中匹配的y元素是哪一个
14 int dx[maxk];
15 int cy[maxk];//记录y集合中匹配的x元素是哪一个
16 int dy[maxk];
17 int vis[maxk];//标记该顶点是否访问过
18 bool searchP(void)    //BFS   
19 {
20     queue <int> Q;
21     dis = INF;
22     memset(dx, -1, sizeof(dx));
23     memset(dy, -1, sizeof(dy));
24     for (int i = 1; i <= Nx; i++)
25         if (cx[i] == -1)
26         {
27             Q.push(i); dx[i] = 0;
28         }
29     while (!Q.empty())
30     {
31         int u = Q.front(); Q.pop();
32         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
33         for (int v = 1; v <= Ny; v++)
34             if (mp[u][v] && dy[v] == -1)
35             {        //v是未匹配点  
36                 dy[v] = dx[u] + 1;
37                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
38                 else
39                 {
40                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
41                     Q.push(cy[v]);
42                 }
43             }
44     }
45     return dis != INF;
46 }
47 
48 bool DFS(int u)
49 {
50     for (int v = 1; v <= Ny; v++)
51         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
52         {
53             vis[v] = 1;
54             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
55             if (cy[v] == -1 || DFS(cy[v]))
56             {     //是增广路径,更新匹配集  
57                 cy[v] = u; cx[u] = v;
58                 return 1;
59             }
60         }
61     return 0;
62 }
63 
64 int MaxMatch()
65 {
66     int res = 0;
67     memset(cx, -1, sizeof(cx));
68     memset(cy, -1, sizeof(cy));
69     while (searchP())
70     {
71         memset(vis, 0, sizeof(vis));
72         for (int i = 1; i <= Nx; i++)
73             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
74     }
75     return res;
76 }
77 
78 int main()
79 {
80     int C;
81     scanf("%d", &C);
82     while (C--)
83     {
84         scanf("%d%d", &n, &m);
85         memset(mp, 0, sizeof(mp));
86         for (int i = 1; i <= m; i++)
87         {
88             int u, v;
89             scanf("%d%d", &u, &v);
90             mp[u][v] = true;
91         }
92         Nx = n, Ny = n;
93         int ans = MaxMatch();
94         printf("%d\n", n-ans);
95     }
96     return 0;
97 }

图片 33图片 34

View Code

  1 #include<iostream>
  2 #include<queue>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<vector>
  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<edge>ans;
 30 
 31 struct Dicnic
 32 {
 33     int n;
 34     bool vis[maxn];
 35     int level[maxn];
 36     int st, ed;
 37     vector<int>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<int>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         else
160         {
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             else
175             {
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 }

10、poj 2594 Treasure
Exploration(最小路径覆盖,可关键)

View Code

   题意:同上一题近似,不过允许多个机器人搜索同一个极限。

 9、uvalive 2957 Bring Them There

  思路:用Folyd,把多个直接相连的终点直接连上。之后思路和上一题类似。

  题意:有N个星球,有M条双向边,须求把K台电脑送S星送到T星。每个飞船只可以装一台总计机,且从一个星星到达另一个星球的大运为1天。问最少的天命?

图片 35图片 36

  思路:首先把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)为啥会出错……)

  1 //题意:选出最小路径覆盖图中所有点,路径可以交叉,也就是允许路径有重复的点。
  2 #include<iostream>
  3 #include<queue>
  4 #include<memory.h>
  5 #include<algorithm>
  6 #include<cmath>
  7 using namespace std;
  8 int n, t, m, Nx, Ny, dis, totalr, totalc;
  9 const int maxn = 50;//最大行数
 10 const int maxm = 15;//最大列数
 11 const int maxk = 550;//x集与y集最多元素
 12 const int INF = 0x7fffffff;
 13 bool mp[maxk][maxk];//1表示该ij可以匹配
 14 int cx[maxk];//记录x集合中匹配的y元素是哪一个
 15 int dx[maxk];
 16 int cy[maxk];//记录y集合中匹配的x元素是哪一个
 17 int dy[maxk];
 18 int vis[maxk];//标记该顶点是否访问过
 19 bool searchP(void)    //BFS   
 20 {
 21     queue <int> Q;
 22     dis = INF;
 23     memset(dx, -1, sizeof(dx));
 24     memset(dy, -1, sizeof(dy));
 25     for (int i = 1; i <= Nx; i++)
 26         if (cx[i] == -1)
 27         {
 28             Q.push(i); dx[i] = 0;
 29         }
 30     while (!Q.empty())
 31     {
 32         int u = Q.front(); Q.pop();
 33         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
 34         for (int v = 1; v <= Ny; v++)
 35             if (mp[u][v] && dy[v] == -1)
 36             {        //v是未匹配点  
 37                 dy[v] = dx[u] + 1;
 38                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
 39                 else
 40                 {
 41                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
 42                     Q.push(cy[v]);
 43                 }
 44             }
 45     }
 46     return dis != INF;
 47 }
 48 
 49 bool DFS(int u)
 50 {
 51     for (int v = 1; v <= Ny; v++)
 52         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
 53         {
 54             vis[v] = 1;
 55             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
 56             if (cy[v] == -1 || DFS(cy[v]))
 57             {     //是增广路径,更新匹配集  
 58                 cy[v] = u; cx[u] = v;
 59                 return 1;
 60             }
 61         }
 62     return 0;
 63 }
 64 
 65 int MaxMatch()
 66 {
 67     int res = 0;
 68     memset(cx, -1, sizeof(cx));
 69     memset(cy, -1, sizeof(cy));
 70     while (searchP())
 71     {
 72         memset(vis, 0, sizeof(vis));
 73         for (int i = 1; i <= Nx; i++)
 74             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
 75     }
 76     return res;
 77 }
 78 
 79 int main()
 80 {
 81     while (~scanf("%d%d", &n, &m))
 82     {
 83         if (n == 0 && m == 0)break;
 84         memset(mp, 0, sizeof(mp));
 85         for (int i = 1; i <= m; i++)
 86         {
 87             int u, v;
 88             scanf("%d%d", &u, &v);
 89             mp[u][v] = true;
 90         }
 91         //解决有重复点的问题~方法就是使用Floyd求闭包,就是把间接相连的点直接连上边,然后就是求最小路径覆盖
 92         for (int k = 1; k <= n; k++)
 93         {
 94             for (int i = 1; i <= n; i++)
 95             {
 96                 for (int j = 1; j <= n; j++)
 97                 {
 98                     if (!mp[i][j] && mp[i][k] && mp[k][j])
 99                     {
100                         mp[i][j] = true;
101                     }
102                 }
103             }
104         }
105         Nx = n, Ny = n;
106         int ans = MaxMatch();
107         printf("%d\n", n - ans);
108     }
109     return 0;
110 }

  出错原因:因为将来的每日都是在原先的残存网络上增边再求最大流,原来就部分边的flow并没有被清。所以每回调用最大流获得的流是当天抵达目标地的货色数,根据累加性质,DFS的maxf应当置为needflow-ret。以上为maxf应当置为needflow-ret的解说,但对INF(比needflow-ret大得多),为啥不可以仍然不曾眉目。。。。

View Code

 

11、hdu 3829 Cat VS Dog
(二分匹配、最大独立集)

图片 37图片 38

  题意:每个娃娃都有喜欢的和不欣赏的某只狗或某只猫(倘使喜欢狗,则不喜欢猫,反之亦然)。现在,动物园管理者想要淘汰部分狗和猫,使得最终神采飞扬的儿女最多(唯有喜欢的那只,不欣赏的那只被淘汰)。

  1 #include<iostream>
  2 #include<queue>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<vector>
  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<int>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 tunnel
122 {
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<int, int>&a, const pair<int, int>&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].to
170                 id += 2;
171                 int flow2 = Edge[id].flow;//从(day - 1)*N + tnl[i].to到day*N + tnl[i].from
172                 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<pair<int, int> >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

图片 39图片 40

 10、uvalive 2531 The K-League
UVALive

  1 //题意:选出最小路径覆盖图中所有点,路径可以交叉,也就是允许路径有重复的点。
  2 #include<iostream>
  3 #include<queue>
  4 #include<memory.h>
  5 #include<algorithm>
  6 #include<cmath>
  7 using namespace std;
  8 int n, t, m,p, Nx, Ny, dis, totalr, totalc;
  9 const int maxn = 110;//最大行数
 10 const int maxm = 110;//最大列数
 11 const int maxp = 550;//x集与y集最多元素
 12 const int INF = 0x7fffffff;
 13 bool mp[maxp][maxp];//1表示该ij可以匹配
 14 int cx[maxp];//记录x集合中匹配的y元素是哪一个
 15 int dx[maxp];
 16 int cy[maxp];//记录y集合中匹配的x元素是哪一个
 17 int dy[maxp];
 18 int vis[maxp];//标记该顶点是否访问过
 19 
 20 struct ps
 21 {
 22     int like;
 23     int u;
 24     int dislike;
 25     int v;
 26 }people[maxp];
 27 
 28 
 29 bool searchP(void)    //BFS   
 30 {
 31     queue <int> Q;
 32     dis = INF;
 33     memset(dx, -1, sizeof(dx));
 34     memset(dy, -1, sizeof(dy));
 35     for (int i = 1; i <= Nx; i++)
 36         if (cx[i] == -1)
 37         {
 38             Q.push(i); dx[i] = 0;
 39         }
 40     while (!Q.empty())
 41     {
 42         int u = Q.front(); Q.pop();
 43         if (dx[u] > dis) break;        //说明该增广路径长度大于dis还没有结束,等待下一次BFS在扩充  
 44         for (int v = 1; v <= Ny; v++)
 45             if (mp[u][v] && dy[v] == -1)
 46             {        //v是未匹配点  
 47                 dy[v] = dx[u] + 1;
 48                 if (cy[v] == -1) dis = dy[v];    //得到本次BFS的最大遍历层次  
 49                 else
 50                 {
 51                     dx[cy[v]] = dy[v] + 1;         //v是匹配点,继续延伸  
 52                     Q.push(cy[v]);
 53                 }
 54             }
 55     }
 56     return dis != INF;
 57 }
 58 
 59 bool DFS(int u)
 60 {
 61     for (int v = 1; v <= Ny; v++)
 62         if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1)
 63         {
 64             vis[v] = 1;
 65             if (cy[v] != -1 && dy[v] == dis) continue;   //层次(也就是增广路径的长度)大于本次查找的dis,是searchP被break的情况,也就是还不确定是否是增广路径,只有等再次调用searchP()在判断。  
 66             if (cy[v] == -1 || DFS(cy[v]))
 67             {     //是增广路径,更新匹配集  
 68                 cy[v] = u; cx[u] = v;
 69                 return 1;
 70             }
 71         }
 72     return 0;
 73 }
 74 
 75 int MaxMatch()
 76 {
 77     int res = 0;
 78     memset(cx, -1, sizeof(cx));
 79     memset(cy, -1, sizeof(cy));
 80     while (searchP())
 81     {
 82         memset(vis, 0, sizeof(vis));
 83         for (int i = 1; i <= Nx; i++)
 84             if (cx[i] == -1 && DFS(i)) res++;   //查找到一个增广路径,匹配数res++  
 85     }
 86     return res;
 87 }
 88 //最大独立集=节点总个数-最小覆盖集,最小覆盖集=最大匹配,所以最大独立集=节点总个数-最大匹配
 89 //如果A喜欢的动物是B不喜欢的动物,或者A不喜欢的动物是B喜欢的动物,那么A、B之间就产生了矛盾,我们就在A和B之间建立一条边,然后求出最多有多少对孩子之间产生矛盾,用这个结果除以2就是最大匹配数。
 90 int main()
 91 {
 92     while (~scanf("%d%d%d", &n, &m,&p))
 93     {
 94         memset(mp, 0, sizeof(mp));
 95 
 96         for (int i = 1; i <= p; i++)
 97         {
 98             int u, v;
 99             char like, dislike;
100             cin >> like >> u >> dislike >> v;
101             if (like == 'C')
102             {
103                 people[i].like = 1;
104                 people[i].u = u;
105                 people[i].dislike = 2;
106                 people[i].v = v;
107             }
108             else
109             {
110                 people[i].like = 2;
111                 people[i].u = u;
112                 people[i].dislike = 1;
113                 people[i].v = v;
114             }
115             
116         }
117         for (int i = 1; i <= p; i++)
118         {
119             for (int j = i + 1; j <= p; j++)
120             {
121                 ps a = people[i], b = people[j];
122                 if (a.dislike == b.like&&a.v == b.u)
123                 {
124                     mp[i][j] = mp[j][i] = true;
125                 }
126                 else if (a.like == b.dislike&&a.u == b.v)
127                 {
128                     mp[i][j] = mp[j][i] = true;
129                 }
130             }
131         }
132         Nx = p, Ny = p;
133         int ans = MaxMatch();
134         printf("%d\n",p - ans/2);
135     }
136     return 0;
137 }

  题意:有n个球队,现在每支球队已经赢了Wi场,输了Di场,并交由两两里边剩余的比赛数,问最后可能胜利的军旅有何样?

View Code

  思路:首先如果第i个球队剩下的场数全部获胜,则totwin=Wi+sum(…),那么我们成立一个顶尖源点和一个至上汇点,从一流源点连到每个匹配(k,j),容量为其多余的场数,并记录总剩余场数tot,而各类匹配能够是k胜利或者j胜利,所以连边,容量为INF;然后因为要确保其余军旅j胜利的总场数不当先球队i可以达成的最大胜利场数totwin,则每只球队j连到一级汇点,容量为其所可以打败的最大场数,即totwin-Wj.最后求最大流,假使最大流刚好等于总剩余场数,表达在装有剩余场数比完事后,球队i可能胜利。

12、poj 2289/hdu 1669  詹米’s Contact
Groups(二分图多重匹配)

图片 41图片 42

  题意:有n个人,有m个群组。每个人都有好多足以进入的群组。现在内需把每个人分配到一个群组,并且分配完成后,保障人数最多的可怜群组的人口最少。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<vector>
  6 #include<cstdio>
  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<int>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<int>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 }

  思路:①转移网络流。建立一个附加源点和汇点。限制每个群组的最大容量,起点与种种人源源不断,每条边容量为1;人和其可以进入的群组连边,容量为1;每个群组和汇点连边,容量为当下所枚举的限定容量。假设在近来限制容量下,最大流为n,则继续尝试收缩限制,否则放大限制。(二分操作)(Dinic算法,借鉴模板)

View Code

图片 43图片 44

 11、uva 10779 Collectors Problem

  1 //网络流二分图多重匹配
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<map>
  7 #include<sstream>
  8 #include<vector>
  9 #include<string>
 10 using namespace std;
 11 
 12 int n, m;
 13 vector<int>pp[1010];
 14 
 15 const int INF = 250000;
 16 /**oo 表示无穷大*/
 17 const int maxe = 1000010;
 18 /**mm 表示边的最大数量,记住要是原图的两倍,在加边的时候都是双向的*/
 19 const int maxn = 1600;
 20 /**mn 表示点的最大数量*/
 21 int nodes, st, ed, edges;
 22 /**node 表示节点数,src 表示源点,dest 表示汇点,edge 统计边数*/
 23 struct node
 24 {
 25     int from;
 26     int to;//边指向的节点
 27     int next;//链表的下一条边
 28     int cap;//边的容量
 29     int flow;//边的流量
 30 }Eg[maxe];
 31 
 32 int head[maxn], work[maxn], level[maxn];
 33 /**head 节点的链表头,work 用于算法中的临时链表头,level 计算层次距离*/
 34 bool vis[maxn];
 35 
 36 /**初始化链表及图的信息*/
 37 void Init(int _node, int _src, int _dest)
 38 {
 39     nodes = _node, st = _src, ed = _dest;
 40     memset(head, -1, sizeof(head));
 41     edges = 0;
 42 }
 43 /**增加一条u 到v 容量为c 的边*/
 44 void addedge(int u, int v, int c)
 45 {
 46     Eg[edges].flow = u, Eg[edges].to = v, Eg[edges].cap = c, Eg[edges].flow = 0, Eg[edges].next = head[u], head[u] = edges++;
 47     Eg[edges].from = v, Eg[edges].to = u, Eg[edges].cap = 0, Eg[edges].flow = 0, Eg[edges].next = head[v], head[v] = edges++;
 48 }
 49 /**广搜计算出每个点与源点的最短距离,如果不能到达汇点说明算法结束*/
 50 void BuildGraph(int mid)
 51 {
 52     Init(n + m + 2, 0, n + m + 1);
 53     for (int i = 1; i <= n; i++) addedge(st, i, 1);
 54     for (int i = n + 1; i <= n + m; i++) addedge(i, ed, mid);
 55     for (int i = 1; i <= n; i++)
 56     {
 57         int sz = pp[i].size();
 58         for (int j = 0; j < sz; j++)
 59         {
 60             addedge(i, pp[i][j], 1);
 61         }
 62     }
 63 }
 64 bool Dinic_bfs()
 65 {
 66     queue<int>q;
 67     int i, u, v;
 68     memset(level, -1, sizeof(level));
 69     memset(vis, 0, sizeof(vis));
 70     q.push(st);
 71     level[st] = 0;
 72     vis[st] = true;
 73     while (!q.empty())
 74     {
 75         u = q.front();
 76         q.pop();
 77         for (i = head[u]; i != -1; i = Eg[i].next)
 78         {
 79             v = Eg[i].to;
 80             if (Eg[i].cap>Eg[i].flow && !vis[v])
 81             {
 82                 vis[v] = true;
 83                 /**这条边必须有剩余容量*/
 84                 level[v] = level[u] + 1;
 85                 if (v == ed)return true;
 86                 q.push(v);
 87             }
 88         }
 89     }
 90     return false;
 91 }
 92 /**寻找可行流的增广路算法,按节点的距离来找,加快速度*/
 93 int Dinic_dfs(int u, int maxf)
 94 {
 95     if (u == ed || maxf == 0)return maxf;
 96     /**work 是临时链表头,这里用i 引用它,这样寻找过的边不再寻找*/
 97     int flow = 0, f;
 98     for (int &i = work[u], v; i != -1; i = Eg[i].next)
 99     {
100         v = Eg[i].to;
101         if (level[v] == level[u] + 1 && (f = Dinic_dfs(v, min(maxf, Eg[i].cap - Eg[i].flow))) > 0)
102         {
103             Eg[i].flow += f;
104             Eg[i ^ 1].flow -= f;
105             /**正反向边容量改变*/
106             flow += f;
107             maxf -= f;
108             if (maxf == 0) break;
109         }
110     }
111     return flow;
112 }
113 int Dinic_flow()
114 {
115     int l = 0, r = 1010,ans,ret;
116     while (l <= r)
117     {
118         int mid = (l + r) / 2;
119         ret = 0;
120         BuildGraph(mid);
121         while (Dinic_bfs())
122         {
123             memcpy(work, head, sizeof(head));
124             ret += Dinic_dfs(st, INF);
125         }
126         if (ret == n)
127         {
128             ans = mid;
129             r = mid - 1;
130         }
131         else
132         {
133             l = mid + 1;
134         }
135     }
136     return ans;
137 }
138 int main()
139 {
140     char name[20];
141     string s;
142     while (~scanf("%d%d", &n, &m))
143     {
144         if (n == 0 && m == 0)break;
145         for (int i = 1; i <= n; i++) pp[i].clear();
146         for (int i = 1; i <= n; i++)
147         {
148             scanf("%s", name);
149             getline(cin, s);
150             stringstream sin(s);
151             int x;
152             while (sin >> x)
153             {
154                 pp[i].push_back(x + 1 + n);
155             }
156         }
157         int ans = Dinic_flow();
158         printf("%d\n", ans);
159     }
160     return 0;
161 }

  题意:Bob有n-1个对象,每个人有Ki张贴纸,贴纸的项目一共有m种。现在,鲍伯(Bob)的心上人只会和鲍勃(Bob)调换自己从不的贴纸,问鲍勃最终收获贴纸的花色最大是稍稍?

View Code

  思路:鲍勃作为起点,对曾经局地贴纸类型建边,容量为其所怀有的该项目标贴纸的数额;每种档次的贴纸向汇点建边,容量为1,表示能不能取得该项目的贴纸;当某个朋友有所某种类型的贴纸的数据大于1时,其得以拿出多少-1那样多的该项目贴纸来调换,则该对象向该品种贴纸建边,容量为对应数目-1;即使情侣没有某种类型的贴纸,则鲍伯可以和其调换1张,则该贴纸类型向心上人建边,容量为1.说到底用Dicnic求最大流即可。

13、poj 2112 Optimal
Milking(二分图多重匹配)

图片 45图片 46

  题意:给出牛和机器间的离开(二维矩阵代表,假使i==j,值为0;假诺无法到达,值也输入为0),现在,在保管拥有牛都能抵达挤奶机械下,使得走得最长的牛的走的离开最小。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<queue>
  6 #include<vector>
  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<int>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+1
125         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 }

  思路:①先用Floyd算出两两间最短距离。然后转换网络流,限制最大距离。建立一个额外源点与汇点,起点和每头牛相连,容量为1;牛和机器间的最短距离小于等于限制距离则连线,容量为1;机器和汇点连线,容量为1.老是二分限制最短距离。(Dinic算法,和上一个存有修改,上一个谬误,不太精通)

View Code

图片 47图片 48

 12、uvalive 3286 Jamie’s Contact
Groups

  1 //网络流二分图多重匹配
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<map>
  7 #include<sstream>
  8 #include<vector>
  9 #include<string>
 10 using namespace std;
 11 
 12 int k, c, m;
 13 
 14 
 15 const int INF = 0x3f3f3f3f;
 16 /**oo 表示无穷大*/
 17 const int maxe = 200000;
 18 /**mm 表示边的最大数量,记住要是原图的两倍,在加边的时候都是双向的*/
 19 const int maxn = 300;
 20 /**mn 表示点的最大数量*/
 21 int nodes, st, ed, edges;
 22 /**node 表示节点数,src 表示源点,dest 表示汇点,edge 统计边数*/
 23 int mp[500][500];
 24 struct node
 25 {
 26     int from;
 27     int to;//边指向的节点
 28     int next;//链表的下一条边
 29     int cap;//边的容量
 30     int flow;//边的流量
 31 }Eg[1000000];
 32 
 33 int head[15500], work[15500], level[15500];
 34 /**head 节点的链表头,work 用于算法中的临时链表头,level 计算层次距离*/
 35 bool vis[15500];
 36 
 37 /**初始化链表及图的信息*/
 38 void Init(int _node, int _src, int _dest)
 39 {
 40     nodes = _node, st = _src, ed = _dest;
 41     memset(head, -1, sizeof(head));
 42     edges = 0;
 43 }
 44 /**增加一条u 到v 容量为c 的边*/
 45 void addedge(int u, int v, int c)
 46 {
 47     Eg[edges].flow = u, Eg[edges].to = v, Eg[edges].cap = c, Eg[edges].flow = 0, Eg[edges].next = head[u], head[u] = edges++;
 48     Eg[edges].from = v, Eg[edges].to = u, Eg[edges].cap = 0, Eg[edges].flow = 0, Eg[edges].next = head[v], head[v] = edges++;
 49 }
 50 /**广搜计算出每个点与源点的最短距离,如果不能到达汇点说明算法结束*/
 51 void BuildGraph(int mid)
 52 {
 53     Init(k+c+2, 0, k + c + 1);
 54     for (int i = 1; i <= k; i++) addedge(i, ed, m);
 55     for (int i = k + 1; i <=k+c; i++) addedge(st,i, 1);
 56     for (int i =k+1; i <= k+c; i++)
 57     {
 58         for (int j = 1; j <=k; j++)
 59         {
 60             if(mp[i][j]<=mid)addedge(i,j, 1);
 61         }
 62     }
 63 }
 64 bool Dinic_bfs()
 65 {
 66     queue<int>q;
 67     int i, u, v;
 68     memset(level, -1, sizeof(level));
 69     memset(vis, 0, sizeof(vis));
 70     q.push(st);
 71     level[st] = 0;
 72     vis[st] = true;
 73     while (!q.empty())
 74     {
 75         u = q.front();
 76         if (u == ed) return true;
 77         q.pop();
 78         for (i = head[u]; i != -1; i = Eg[i].next)
 79         {
 80             v = Eg[i].to;
 81             if (Eg[i].cap>Eg[i].flow && !vis[v]&&level[v]==-1)
 82             {
 83                 vis[v] = true;
 84                 /**这条边必须有剩余容量*/
 85                 level[v] = level[u] + 1;
 86                 q.push(v);
 87             }
 88         }
 89     }
 90     return false;
 91 }
 92 /**寻找可行流的增广路算法,按节点的距离来找,加快速度*/
 93 int Dinic_dfs(int u, int maxf)
 94 {
 95     if (u == ed)return maxf;
 96     /**work 是临时链表头,这里用i 引用它,这样寻找过的边不再寻找*/
 97     int flow = 0, f;
 98     for (int &i = work[u], v; i != -1; i = Eg[i].next)
 99     {
100         v = Eg[i].to;
101         if (Eg[i].cap - Eg[i].flow>0&&level[v] == level[u] + 1)
102         {
103             f = Dinic_dfs(v, min(maxf, Eg[i].cap - Eg[i].flow));
104             Eg[i].flow += f;
105             Eg[i ^ 1].flow -= f;
106             /**正反向边容量改变*/
107             flow += f;
108             if (flow == maxf) return flow;
109         }
110     }
111     return flow;
112 }
113 int Dinic_flow()
114 {
115     int l = 0, r = 10000, ans, ret;
116     while (l <= r)
117     {
118         int mid = (l + r) / 2;
119         ret = 0;
120         BuildGraph(mid);
121         while (Dinic_bfs())
122         {
123             memcpy(work, head, sizeof(head));
124             ret += Dinic_dfs(st, INF);
125         }
126         if (ret == c)
127         {
128             ans = mid;
129             r = mid - 1;
130         }
131         else
132         {
133             l = mid + 1;
134         }
135     }
136     return ans;
137 }
138 int main()
139 {
140     while (~scanf("%d%d%d", &k, &c, &m))
141     {
142         for (int i = 1; i <= k + c; i++)
143         {
144             for (int j = 1; j <= k + c; j++)
145             {
146                 scanf("%d", &mp[i][j]);
147                 if (i!=j&&mp[i][j] == 0) mp[i][j] = INF;
148             }
149         }
150         for (int z = 1; z <= k + c; z++)
151         {
152             for (int i = 1; i <= k + c; i++)
153             {
154                 for (int j = 1; j <= k + c; j++)
155                 {
156                     mp[i][j] = min(mp[i][j], mp[i][z] + mp[z][j]);
157                 }
158             }
159         }
160         int ans = Dinic_flow();
161         printf("%d\n", ans);
162     }
163 
164     return 0;
165 }

  题意:有n个人,有m个组别,每个人摘取部分分别出席,但不得不进入其中的一个。问,所有人分组后,人数最多的分其外人头最小是不怎么?

View Code

  思路:设置源点连向每一个人,权值为1,表示每个人都足以挑选进入一个区分;每个人连向其所能出席的界别,权值为1;之后二分最大区其余人数,设其为tmpmax,从各种界别连向汇点,表示最七只可以接纳tmpmax这么多的人进入,然后求最大流,当==n时看看能如故不能够让tmpmax减弱。

14、poj 3189 Steady Cow Assignment

图片 49图片 50

  题意:有n头牛,b个畜棚。给出每头牛根据喜欢程度的优先级从大到小的牛棚编号,再提交每个牛棚的容量。求某一种分配下,在装有牛中,其分到的牛棚的最大优先级和压低优先级之差最小。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 #include<string>
  7 #include<sstream>
  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<int>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+1
121         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             else
153             {
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 }

  思路:①变换网络流,限制最大优先级和先行级之差,对于每一个范围,枚举其可能的界定(比如有4个牛棚,限制差值为2,则可能的优先级范围为[1,3]或[2,4])。建立额外的源点和汇点,起点和每头牛相连,容量为1;牛与其所划分优先级的限量内的牛棚连线,容量为1;每个牛棚和汇点相连,容量为牛棚各自的最大容纳牛的多寡。求最大流。

View Code

图片 51图片 52

 13、uva 11082 Matrix
Decompressing

  1 #include<stdio.h>
  2 #include<queue>
  3 #include<string.h>
  4 #include<iostream>
  5 using namespace std;
  6 #define INF 0x3f3f3f3f
  7 const int maxe = 300000;
  8 const int maxn = 2000;
  9 const int maxb = 100;
 10 const int maxnodes = 2000;
 11 int head[maxnodes];
 12 int level[maxnodes];
 13 int cur[maxnodes];
 14 
 15 struct node
 16 {
 17     int from;
 18     int to;
 19     int w;
 20     int next;
 21 }e[maxe];
 22 int map[maxn][maxb];
 23 int barns[maxb];
 24 int b, n, st, ed, cont;
 25 void addeg(int from, int to, int w)
 26 {
 27     e[cont].from = from;
 28     e[cont].to = to;
 29     e[cont].w = w;
 30     e[cont].next = head[from];
 31     head[from] = cont++;
 32     e[cont].from = to;//反向建边
 33     e[cont].to = from;
 34     e[cont].w = 0;
 35     e[cont].next = head[to];
 36     head[to] = cont++;
 37 }
 38 void getmap(int x, int y)
 39 {
 40     st = 0;
 41     ed = n + b + 1;
 42     cont = 0;
 43     memset(head, -1, sizeof(head));
 44     for (int i = 1; i <= n; i++) addeg(st, i, 1);
 45     for (int i = n + 1; i <= n + b; i++) addeg(i, ed, barns[i - n]);
 46     for (int i = 1; i <= n; i++)
 47     {
 48         for (int j = x; j <= y; j++)
 49         {
 50             addeg(i, n + map[i][j], 1);
 51         }
 52     }
 53 }
 54 int BFS()
 55 {
 56     memset(level, 0, sizeof(level));
 57     queue<int>s;
 58     s.push(st);
 59     level[st] = 1;
 60     while (!s.empty())
 61     {
 62         int u = s.front();
 63         if (u == ed)return 1;
 64         s.pop();
 65         for (int i = head[u]; i != -1; i = e[i].next)
 66         {
 67             int v = e[i].to;
 68             int w = e[i].w;
 69             if (w&&level[v] == 0)
 70             {
 71                 level[v] = level[u] + 1;
 72                 s.push(v);
 73             }
 74         }
 75     }
 76     return 0;
 77 }
 78 int Dfs(int u, int maxflow, int tt)
 79 {
 80     if (u == tt)return maxflow;
 81     int ret = 0;
 82     for (int &i = cur[u]; i != -1; i = e[i].next)
 83     {
 84         int v = e[i].to;
 85         int w = e[i].w;
 86         if (w&&level[v] == level[u] + 1)
 87         {
 88             int f = Dfs(v, min(maxflow - ret, w), tt);
 89             e[i].w -= f;
 90             e[i ^ 1].w += f;
 91             ret += f;
 92             if (ret == maxflow)return ret;
 93         }
 94     }
 95     return ret;
 96 }
 97 int Dinic(int x, int y)
 98 {
 99     getmap(x, y);
100     int ans = 0;
101     while (BFS())
102     {
103         memcpy(cur, head, sizeof(head));
104         ans += Dfs(st, INF, ed);
105     }
106     if (ans == n)return 1;
107     else return 0;
108 }
109 int main()
110 {
111     while (~scanf("%d%d", &n, &b))
112     {
113         for (int i = 1; i <= n; i++)
114         {
115             for (int j = 1; j <= b; j++)
116             {
117                 scanf("%d", &map[i][j]);
118             }
119         }
120         for (int i = 1; i <= b; i++) scanf("%d", &barns[i]);
121         int ans = INF;
122         bool flag = true;
123         for (int len = 1; flag&& len <= b; len++)
124         {
125             for (int i = 1; flag&&i + len - 1 <= b; i++)
126             {
127                 if (Dinic(i, i + len - 1))
128                 {
129                     ans = len;
130                     flag = false;
131                     break;
132                 }
133             }
134         }
135         printf("%d\n", ans);
136     }
137 }

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

View Code

  思路:因为限制矩阵元素的轻重缓急,所以当行连向列时,如果每条边已经足足为1,那么边权能够设为19,然后输出时+1即可。然后从源点连向行i,边权为SUMRi-C;从列连向汇点,边权为SUMCi-R.Dicnic求最大流即可。

15、poj 3436 ACM Computer Factory

图片 53图片 54

  题意:大家需求装配p个配件。每台机器都有自己的界定(满意进入限制条件(不可以有怎么样零件0、必需求有怎么样零件1、哪些零件可有可无2)后才能加工该半成品,加工后则会略微零件具备1,有些零件没具备0)。同时,每台机器有各自的频率。问怎么着设置加工流使得最后总作用最大。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #include<cstdio>
  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<int>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+1
129         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 }

  思路:最大流。建立起源(什么零件都尚未)和汇点(什么零件都有)。同时把每台机器分成八个点,一个输入,一个出口。惟有满足输出输入关系的两样机器才能连线,容量为INF。对于同一台机械,从输入连到输出,容量为功用。起点和满意输入条件的机器不断,容量为INF;机器输出后满意汇点需求的输出口和汇点相连,容量为INF,求一遍最大流。(Edmonds_Karp算法模板)

View Code

图片 55图片 56

 14、uvalive 3645 Objective 
Berlin

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<queue>
  4 using namespace std;
  5 int p, n,st,ed;
  6 const int maxn = 55;
  7 const int maxp = 15;
  8 const int maxe = 10000;
  9 const int INF = 0x7fffffff;
 10 
 11 struct line
 12 {
 13     int u;
 14     int v;
 15     int f;
 16 }lines[maxe];
 17 
 18 int in[maxn][maxp];//记录每台机器的输入要求
 19 int out[maxn][maxp];//记录每台机器的输出情况
 20 int k[maxn];//记录每台机器的最大组装效率
 21 
 22 int mp[maxn * 2][maxn * 2];//网络图
 23 int mptmp[maxn * 2][maxn * 2];//初始图备份
 24 
 25 int prepath[maxn * 2];
 26 int flow[maxn * 2];
 27 bool vis[maxn * 2];
 28 int BFS()
 29 {
 30     queue<int>q;
 31     memset(prepath, 0, sizeof(prepath));
 32     memset(vis, 0, sizeof(vis));
 33     prepath[st] = st;
 34     flow[st] = INF;
 35     q.push(st);
 36     vis[st] = true;
 37     while (!q.empty())
 38     {//可以用优先队列优化
 39         int t = q.front();
 40         q.pop();
 41         if (t == ed)break;
 42         for (int i = 1; i <= n*2+1; i++)
 43         {
 44             if (i != st&&!vis[i]&& mp[t][i])
 45             {
 46                 vis[i] = true;//防止走反向
 47                 flow[i] = flow[t] < mp[t][i] ? flow[t] : mp[t][i];
 48                 q.push(i);
 49                 prepath[i] = t;
 50             }
 51         }
 52     }
 53     if (prepath[ed] == 0) return -1;
 54     else return flow[ed];
 55 }
 56 
 57 int Edmonds_Karp()
 58 {
 59     int maxflow = 0, dflow, cur, pre;
 60     while (1)
 61     {
 62         dflow = BFS();
 63         if (dflow == -1)break;
 64         maxflow += dflow;
 65         cur = ed;
 66         while (cur != st)
 67         {
 68             pre = prepath[cur];
 69             mp[pre][cur] -= dflow;//更新正向边
 70             mp[cur][pre] += dflow;//添加反向边
 71             cur = pre;
 72         }
 73     }
 74     return maxflow;
 75 }
 76 
 77 int main()
 78 {
 79     while (~scanf("%d%d", &p, &n))
 80     {
 81         memset(mp, 0, sizeof(mp));
 82         st = 0, ed = 2 * n + 1;
 83         for (int i = 1; i <= n; i++)
 84         {
 85             scanf("%d", &k[i]);
 86             for (int j = 1; j <= p; j++)
 87             {
 88                 scanf("%d", &in[i][j]);
 89             }
 90             for (int j = 1; j <= p; j++)
 91             {
 92                 scanf("%d", &out[i][j]);
 93             }
 94             mp[i][i + n] = k[i];
 95         }
 96         for (int i = 1; i <= n; i++)
 97         {
 98             for (int j = 1; j <= n; j++)
 99             {
100                 if (i == j) continue;
101                 bool flag = true;
102                 for (int k = 1; k <= p; k++)
103                 {
104                     if (out[i][k] + in[j][k] == 1)
105                     {
106                         flag = false;
107                         break;
108                     }
109                 }
110                 if (flag) mp[i + n][j] = INF;
111             }
112         }
113         for (int i = 1; i <= n; i++)
114         {
115             bool flag = true;
116             for (int j = 1; j <= p; j++)
117             {
118                 if (in[i][j] == 1)
119                 {
120                     flag = false;
121                     break;
122                 }
123             }
124             if (flag)mp[st][i] = INF;
125         }
126         for (int i = 1; i <= n; i++)
127         {
128             bool flag = true;
129             for (int j = 1; j <= p; j++)
130             {
131                 if (out[i][j] == 0)
132                 {
133                     flag = false;
134                     break;
135                 }
136             }
137             if (flag) mp[i + n][ed] = INF;
138         }
139         memcpy(mptmp, mp, sizeof(mp));
140         int ans = Edmonds_Karp();
141         int totaline = 0;
142         for (int i = 1; i <= n; i++)
143         {
144             for (int j = 1; j <= n; j++)
145             {
146                 if (mptmp[i + n][j] > mp[i + n][j])
147                 {
148                     lines[totaline].u = i;
149                     lines[totaline].v = j;
150                     lines[totaline].f = mptmp[i + n][j] - mp[i + n][j];
151                     totaline++;
152                 }
153             }
154         }
155         printf("%d %d\n", ans, totaline);
156         for (int i = 0; i < totaline; i++)
157         {
158             printf("%d %d %d\n", lines[i].u, lines[i].v, lines[i].f);
159         }
160     }
161     return 0;
162 }

  题意:有好多座城池,他们之间有n条航线,每条航线的信息包括起初点、终点、起初时间、到达时刻、游客人数。当到达一座城市后,想要乘另一条航线离开至少要过30分钟。问在停止时间前从给定的一个都会前往给定的另一个都会的最大游客数量。

View Code

  思路:将每条航线i拆成多个点2*i-1和2*i,前者表示从该航道源点站离开,后者表示从该航线终点站到达,前者向后者建边,容量为乘客数量;若是某条航路的起源站为给定的出发城市,则从汇点向其源点站建边,容量为INF;即使某条航路的终点站为给定的前往城市,则从其终点站向汇点建边,容量为INF;假若某条航路到达后起码过30分钟后可以乘另一条航线离开,则前者的终点站向后者的源点站建边,容量为INF。Dicnic求最大流即可。注意建边时航线的到达时间不应当迟于甘休时间。

16、poj 3281 Dining

图片 57图片 58

  题意:每头牛都有温馨喜欢的若干个食物(编号)和爱好的多少个饮料(编号)。可是每种食品或每种饮品都只能给一头牛。求饮料和食品都可以得到的牛的最大个数。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<queue>
  4 #include<map>
  5 #include<string>
  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<int>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<string, int>mp;
102 char name[15];
103 char stname[15], edname[15];
104 struct fly
105 {
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 }

  思路:最大流。建立起源和汇点。起点和每种食品相连,容量为1;把每头牛拆成多少个点(一个三番五次食品<左牛>,一个总是饮料<右牛>),同一头牛的五个点时期连线,容量为1;把食物和欣赏该食物的那头牛的左牛连线,容量为1;把右牛和该牛喜欢的饮品连线,容量为1;把富有饮料连向汇点,容量为1.求三次最大流。(Edmonds_Karp算法模板)

View Code

图片 59图片 60

 15、uvalive 4597/uva 1440
Inspection

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 using namespace std;
  5 int n, f, d,st,ed;
  6 const int maxn = 450;
  7 const int maxe = 250000;
  8 const int INF = 0x7fffffff;
  9 
 10 int mp[maxn][maxn];
 11 int level[maxn];//分层
 12 int vis[maxn];
 13 int flow[maxn];
 14 int prepath[maxn];
 15 
 16 int BFS()
 17 {
 18     queue<int>q;
 19     memset(prepath, 0, sizeof(prepath));
 20     memset(vis, 0, sizeof(vis));
 21     prepath[st] = st;
 22     flow[st] = INF;
 23     q.push(st);
 24     vis[st] = true;
 25     while (!q.empty())
 26     {//可以用优先队列优化
 27         int t = q.front();
 28         q.pop();
 29         if (t == ed)break;
 30         for (int i = 1; i <=ed; i++)
 31         {
 32             if (i != st && !vis[i] && mp[t][i])
 33             {
 34                 vis[i] = true;//防止走反向
 35                 flow[i] = flow[t] < mp[t][i] ? flow[t] : mp[t][i];
 36                 q.push(i);
 37                 prepath[i] = t;
 38             }
 39         }
 40     }
 41     if (prepath[ed] == 0) return -1;
 42     else return flow[ed];
 43 }
 44 
 45 int Edmonds_Karp()
 46 {
 47     int maxflow = 0, dflow, cur, pre;
 48     while (1)
 49     {
 50         dflow = BFS();
 51         if (dflow == -1)break;
 52         maxflow += dflow;
 53         cur = ed;
 54         while (cur != st)
 55         {
 56             pre = prepath[cur];
 57             mp[pre][cur] -= dflow;//更新正向边
 58             mp[cur][pre] += dflow;//添加反向边
 59             cur = pre;
 60         }
 61     }
 62     return maxflow;
 63 }
 64 
 65 
 66 int main()
 67 {
 68     while (~scanf("%d%d%d", &n, &f, &d))
 69     {
 70         //建图
 71         st = 0, ed = 2 * n + f + d + 1;
 72         memset(mp, 0, sizeof(mp));
 73         for (int i = 1; i <= n; i++)
 74         {
 75             mp[i][i + n] = 1;//每头牛拆点,左牛到右牛
 76             int fi, di;
 77             scanf("%d%d", &fi, &di);
 78             for (int j = 1; j <= fi; j++)
 79             {
 80                 int ff;
 81                 scanf("%d", &ff);
 82                 mp[2 * n + ff][i] = 1;//食物到左牛
 83             }
 84             for (int j = 1; j <= di; j++)
 85             {
 86                 int dd;
 87                 scanf("%d", &dd);
 88                 mp[i + n][2 * n + f + dd] = 1;//右牛到饮料
 89             }
 90             
 91         }
 92         for (int i = 1; i <= f; i++) mp[0][2 * n + i] = 1;//源点到食物
 93         for (int j = 1; j <= d; j++)mp[2 * n + f + j][2 * n + f + d + 1] = 1;//饮料到汇点
 94 
 95         //Edmonds_Karp算法
 96         int ans = Edmonds_Karp();
 97 
 98         printf("%d\n", ans);
 99     }
100     return 0;
101 }

  题意:有一座山上修建了成千成万滑雪的大路,有n个点构成有向无环图。现在您可以随意从一个源点出发,到达另一个方可抵达的点,记为一条路子。求用最少的途径,有限支撑每条边都至少走过一遍。

View Code

  思路:有下限的矮小流。首先选取出度大于入度的点作为起源,入度大于出度的点作为终点。然后因为每条边能够走很多次。那么一旦想要走过所有的边,则至多有sum(abs(入度-出度))条路线。出度大于入度的点连向汇点,起源连向入度大于出度的点,其最大流为可以减弱的路径数,并且可以取得每条正向边所要多走的次数(即其flow值),该值须要添加至入度或出度(表示可以多走)。然后用dfs,当出度-入度>0时,表示可以伸张出一条途径,dfs深搜可以走的点,并且修改入度和出度。那里可以用一个数组记录入度-出度的数值,以福利运算。

17、poj 1273 Drainage Ditches

参照博客:https://www.cnblogs.com/dwtfukgv/p/7780903.htmlhttp://blog.csdn.net/fuxey/article/details/50472528http://blog.csdn.net/sdj222555/article/details/40380423

  题意:有n个沟渠,m个结点(编号为1的为池塘,编号为m的为溪流)。每个渠道都有温馨的最大流速,问从池子到溪流的最大排水流速。

图片 61图片 62

  思路:起点为池塘,汇点为溪流。依据沟渠的走向和流速建立图,求最大流。基础题。(Edmonds_Karp算法模板)

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 #include<vector>
  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<int>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<int>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);//每条边可以走多次,所以容量为INF
125                 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 }

图片 63图片 64

View Code

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 
 5 const int INF = 0x7fffffff;
 6 int V, E;
 7 int level[205];
 8 int Si, Ei, Ci;
 9 
10 struct Dinic
11 {
12     int c;
13     int f;
14 }edge[205][205];
15 
16 bool dinic_bfs()      //bfs方法构造层次网络
17 {
18     queue<int> q;
19     memset(level, 0, sizeof(level));
20     q.push(1);
21     level[1] = 1;
22     int u, v;
23     while (!q.empty())
24     {
25         u = q.front();
26         q.pop();
27         for (v = 1; v <= E; v++)
28         {
29             if (!level[v] && edge[u][v].c>edge[u][v].f)
30             {
31                 level[v] = level[u] + 1;
32                 q.push(v);
33             }
34         }
35     }
36     return level[E] != 0;                //question: so it must let the sink node is the Mth?/the way of yj is give the sink node's id
37 }
38 
39 int dinic_dfs(int u, int cp)
40 {           //use dfs to augment the flow
41     int tmp = cp;
42     int v, t;
43     if (u == E)
44         return cp;
45     for (v = 1; v <= E&&tmp; v++)
46     {
47         if (level[u] + 1 == level[v])
48         {
49             if (edge[u][v].c>edge[u][v].f)
50             {
51                 t = dinic_dfs(v, min(tmp, edge[u][v].c - edge[u][v].f));
52                 edge[u][v].f += t;
53                 edge[v][u].f -= t;
54                 tmp -= t;
55             }
56         }
57     }
58     return cp - tmp;
59 }
60 int dinic()
61 {
62     int sum = 0, tf = 0;
63     while (dinic_bfs())
64     {
65         while (tf = dinic_dfs(1, INF))
66             sum += tf;
67     }
68     return sum;
69 }
70 
71 int main()
72 {
73     while (scanf("%d%d", &V, &E))
74     {
75         memset(edge, 0, sizeof(edge));
76         while (V--)
77         {
78             scanf("%d%d%d", &Si, &Ei, &Ci);
79             edge[Si][Ei].c += Ci;
80         }
81         int ans = dinic();
82         printf("%d\n", ans);
83     }
84     return 0;
85 }

 16、uvalive 3487 Duopoly

View Code

  题意:有两家商厦分别对拍卖会上的channel举行竞价,分别交付每一组的付出价格和该组所富含的channel(表示用如此多的钱购置该组所有的channel)。不过对于两家商店顶牛的bid,只好拔取接受其中一家的竞价,即每一个channel只好被一家集团所有,求拍卖所得最大利润?

 18、poj 1087/uva 753 A Plug for
UNIX

  思路:要是两家没有争论的地点,则最大利润则是格子出价之和。假若有龃龉,则一定拔取利润高的,扔掉代价小的。将有龃龉的两家的bid相连,之后求最大流,最终取得最大流的值为所要扔掉的有着的代价。

  题意:房间内有n个插座板,有m个设备,有k种接口转换器,求最少有多少设备不可能插进插座。

图片 65图片 66

  思路:最大流。关键是建图。见代码注释。Dinic算法。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<queue>
  6 #include<vector>
  7 #include<string>
  8 #include<sstream>
  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>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<int>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 }

图片 67图片 68

View Code

  1 #include<iostream>
  2 #include<queue>
  3 #include<map>
  4 #include<string>
  5 using namespace std;
  6 const int INF = 0x3f3f3f3f;
  7 struct node
  8 {
  9     int from;
 10     int to;//边指向的节点
 11     int next;//链表的下一条边
 12     int cap;//边的容量
 13     int flow;//边的流量
 14 }Eg[100000];
 15 
 16 int head[1000], work[1000], level[1000];
 17 /**head 节点的链表头,work 用于算法中的临时链表头,level 计算层次距离*/
 18 bool vis[15500];
 19 int edges, st, ed,nodes;
 20 int n,m,k;
 21 map<string, int>gid;
 22 int rpt[110];//房间有哪些类型插座
 23 int devices[110];//用电器插头类型
 24 int adp[110][2];//转接器
 25 /**初始化链表及图的信息*/
 26 void Init(int _node, int _src, int _dest)
 27 {
 28     nodes = _node, st = _src, ed = _dest;
 29     memset(head, -1, sizeof(head));
 30     edges = 0;
 31 }
 32 /**增加一条u 到v 容量为c 的边*/
 33 void addedge(int u, int v, int c)
 34 {
 35     Eg[edges].from = u, Eg[edges].to = v, Eg[edges].cap = c, Eg[edges].flow = 0, Eg[edges].next = head[u], head[u] = edges++;
 36     Eg[edges].from = v, Eg[edges].to = u, Eg[edges].cap = 0, Eg[edges].flow = 0, Eg[edges].next = head[v], head[v] = edges++;
 37 }
 38 /**广搜计算出每个点与源点的最短距离,如果不能到达汇点说明算法结束*/
 39 void BuildGraph(int cnt)
 40 {
 41     //源点为0,房间插座为1~n,用电器为n+1~n+m,转接器为n+m+1~n+m+k,汇点为n+m+k+1.从插座往插头连线
 42     Init(n+m+k+1, 0,n+m+k+1);
 43     //源点和插座连接
 44     for (int i = 1; i <= n; i++) addedge(st, i, 1);
 45     //用电器到汇点
 46     for (int i = 1; i <= m; i++) addedge(n+i, ed, 1);
 47     //插座到用电器(若可以直连)
 48     for (int i = 1; i <= m; i++)
 49     {
 50         if (devices[i] <= n) addedge(devices[i], n + i, 1);
 51     }
 52     //插座到转换器插头
 53     for (int i = 1; i <= k; i++)
 54     {
 55         if (adp[i][1] <= n) addedge(adp[i][1], n + m + i, INF);
 56     }
 57     //转换器插孔到转换器插头
 58     for (int i = 1; i <= k; i++)
 59     {
 60         for (int j = 1; j <= k; j++)
 61         {
 62             if (i != j&&adp[i][0] == adp[j][1])
 63             {
 64                 addedge(n + m + i, n + m + j,INF);
 65             }
 66         }
 67     }
 68     //转换器插孔到用电器
 69     for (int i = 1; i <= k; i++)
 70     {
 71         for (int j = 1; j <= m; j++)
 72         {
 73             if (adp[i][0] == devices[j])
 74             {
 75                 addedge(n + m + i, n + j, INF);
 76             }
 77         }
 78     }
 79 }
 80 bool Dinic_bfs()
 81 {
 82     queue<int>q;
 83     int i, u, v;
 84     memset(level, -1, sizeof(level));
 85     memset(vis, 0, sizeof(vis));
 86     q.push(st);
 87     level[st] = 0;
 88     vis[st] = true;
 89     while (!q.empty())
 90     {
 91         u = q.front();
 92         if (u == ed) return true;
 93         q.pop();
 94         for (i = head[u]; i != -1; i = Eg[i].next)
 95         {
 96             v = Eg[i].to;
 97             if (Eg[i].cap>Eg[i].flow && !vis[v] && level[v] == -1)
 98             {
 99                 vis[v] = true;
100                 /**这条边必须有剩余容量*/
101                 level[v] = level[u] + 1;
102                 q.push(v);
103             }
104         }
105     }
106     return false;
107 }
108 /**寻找可行流的增广路算法,按节点的距离来找,加快速度*/
109 int Dinic_dfs(int u, int maxf)
110 {
111     if (u == ed)return maxf;
112     /**work 是临时链表头,这里用i 引用它,这样寻找过的边不再寻找*/
113     int flow = 0, f;
114     for (int &i = work[u], v; i != -1; i = Eg[i].next)
115     {
116         v = Eg[i].to;
117         if (Eg[i].cap - Eg[i].flow>0 && level[v] == level[u] + 1)
118         {
119             f = Dinic_dfs(v, min(maxf, Eg[i].cap - Eg[i].flow));
120             Eg[i].flow += f;
121             Eg[i ^ 1].flow -= f;
122             /**正反向边容量改变*/
123             flow += f;
124             if (flow == maxf) return flow;
125         }
126     }
127     return flow;
128 }
129 int Dinic_flow()
130 {
131     int ret = 0;
132     while (Dinic_bfs())
133     {
134         memcpy(work, head, sizeof(head));
135         ret += Dinic_dfs(st, INF);
136     }
137     return ret;
138 }
139 int main()
140 {
141     string s;
142     while (~scanf("%d",&n))
143     {
144         int cnt = 1;
145         for (int i = 1; i <= n; i++)
146         {
147             cin >> s;
148             if (!gid[s])
149             {
150                 gid[s] = cnt++;
151             }
152         }
153         n = cnt - 1;
154         //房间插座编号1~n
155         scanf("%d", &m);
156         for (int i = 1; i <= m; i++)
157         {
158             cin >> s;
159             cin >> s;
160             if (!gid[s]) gid[s] = cnt++;
161             int pos = gid[s];
162             devices[i] = pos;
163         }//设备编号n+1~n+m
164         scanf("%d", &k);
165         for (int i = 1; i <= k; i++)
166         {
167             cin >> s;
168             if (!gid[s]) gid[s] = cnt++;
169             int ff = gid[s];
170             cin >> s;
171             if (!gid[s]) gid[s] = cnt++;
172             int tt = gid[s];
173             adp[i][0] = ff;
174             adp[i][1] = tt;
175         }
176         BuildGraph(cnt);
177         printf("%d\n", m-Dinic_flow());
178     }
179     return 0;
180 }

 

View Code

 

 

相关文章