专题的配合、网络流(一)网络流(注:题意翻译与思路基本都是摘录的人家的(虽然可能有些题目会是投机全然独立做下的,但是题解一般还无会见是自己之,人懒没办法))

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

从今本开班拿各级一个自己认为对自家吧有新意的图论题目汇集下来

  题意:一共有n个学生,m对关系:A认识B。问是否将兼具的人数分成两批判,每批之间的人口犹彼此认识,如果得以,输出每批的口。即判断是否也次分叉图,以及呼吁其次细分图的极致要命匹配。

ps:今意识了一个充分重要的常识我前还直接没有在意到:对一个图第一周跑不过老流动结果是最好深流动,如果还继续跑第二布满,结果碰头是0,很容易了解的地方,我竟直接从未留神到。

  思路:判断是否也次私分图(DFS或BFS);求其次区划图的尽充分匹配:匈牙利算法。

出于当下为主就见面网络流,就先行来网络流的吧:

必威 1必威 2

1.hdu2883

 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 }

题意: 有一个烧烤机,每次最好多能烤 m 块肉,现在发生 n
个人来置办烤肉,每个人至时啊 si,离开时为 ei,点的烤肉数量也
ci,点的烤肉所需要烘烤时间呢 di,

View Code

         
每个人要是烤的肉可分为多卖在同时烤,问是否是一样种方案可以满足所有消费者之求。

2、hdu 1083 Courses(最酷匹配)

解析: 将所有的抵达时和结束时仍升序排序,得到 x <= 2n-1
独时刻距离。

  题意:有P种课程,N个学生。接下来P行,第i执第一单Ni表示喜爱第i只科目的学习者的人口,接下去是Ni个学生。问:能否来一样栽匹配使得每个学员都挑同流派不同之学科,同时兼有科目都出现。

          建图:

  思路:二瓜分图太特别匹配,匈牙利算法,课程为x集,学生吧y集。判断最可怜匹配数是否为P。

          s为源,t为汇,

必威 3必威 4

          每个顾客i作为一个结点并连边(s, i, ni*ti)

 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 }

          每个区间j作为一个结点并连边(j, t, (ej-sj)*M),其中sj,
ej分别代表区间j的苗头时间及已时

View Code

          对擅自顾客i和间隔j,若 [sj, ej] 完全含在 [si, ei]
之中,则连边(i, j, INF)

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

          若太充分流等于 ∑ni*ti 则是 Yes,否则是 No。

  题意:所有棋子不克同行要同列。给起棋可以放大的职,问尽多会扩几单,同时给出重要点(去丢某个位置后哪怕无法担保推广尽量多的棋)的个数。

顿时书我是认为无正确的,比如同组数:

  思路:x集代表行,y集代表列,对于好加大之职(x,y)将x和y连一漫漫边。最多能放之棋子即该二分图的极深匹配。接下来每次去丢一个岗位看看最充分匹配是否非更换,如果转则也重要点。

1 10

必威 5必威 6

1 2 3 5

 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 }

消费者而之事物而五分钟烤完,然后您特么的为家等了2分钟即吓了,你是怎形成的呀O__O
“…

View Code

本,如果确如比较真的言语就书我就算无会见做了(捂脸)

4、HDU 2819 Swap(最可怜匹配)

代码:

  题意:给出n*n的矩阵,问能否通过交换某片行还是某某片列若干次等后,使得那针对性角线上元素都为1.

必威 7必威 8

  思路:只交换行或单独交换列均只是上同等的机能(如果达不顶,说明无解)。列既作x集,也当作y集,[i][j]连线表示用第j排和第i列互换(当[x][y]为1时,将[x][y]连线,表示以可以其更换到[x][x])。然后要者二划分图的无限深匹配。输出每个匹配时,注意交换,否则会多输出。匈牙利算法。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 370000
  8 #define MAXP 606
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Cust
 17 {
 18     int start,last,stay;
 19 }cust[MAXP];
 20 int head[MAXP];
 21 int time[MAXP*2];
 22 int stay[MAXP];
 23 int cur[MAXP];
 24 int pre[MAXP];
 25 int stack[MAXE];
 26 int used[MAXP];
 27 int ent;
 28 int n,m,s,t;
 29 int num;
 30 void add(int start,int last,int f)
 31 {
 32     edge[ent].s=start;
 33     edge[ent].t=last;
 34     edge[ent].f=f;
 35     edge[ent].next=head[start];
 36     head[start]=ent++;
 37     edge[ent].s=last;
 38     edge[ent].t=start;
 39     edge[ent].f=0;
 40     edge[ent].next=head[last];
 41     head[last]=ent++;
 42 }
 43 bool bfs(int S,int T)
 44 {
 45     memset(pre,-1,sizeof(pre));
 46     pre[S]=0;
 47     queue<int>q;
 48     q.push(S);
 49     while(!q.empty())
 50     {
 51         int temp=q.front();
 52         q.pop();
 53         for(int i=head[temp]; i!=-1; i=edge[i].next)
 54         {
 55             int temp2=edge[i].t;
 56             if(pre[temp2]==-1&&edge[i].f)
 57             {
 58                 pre[temp2]=pre[temp]+1;
 59                 q.push(temp2);
 60             }
 61         }
 62     }
 63     return pre[T]!=-1;
 64 }
 65 int dinic(int start,int last)
 66 {
 67     int flow=0,now;
 68     while(bfs(start,last))
 69     {
 70         int top=0;
 71         memcpy(cur,head,sizeof(head));
 72         int u=start;
 73         while(1)
 74         {
 75             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 76             {
 77                 int minn=INT_MAX;
 78                 for(int i=0; i<top; i++)
 79                 {
 80                     if(minn>edge[stack[i]].f)
 81                     {
 82                         minn=edge[stack[i]].f;
 83                         now=i;
 84                     }
 85                 }
 86                 for(int i=0;i<top;i++)
 87                 {
 88                     edge[stack[i]].f-=minn;
 89                     edge[stack[i]^1].f+=minn;
 90                 }
 91                 flow+=minn;
 92                 top=now;
 93                 u=edge[stack[top]].s;
 94             }
 95             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 96                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 97                     break;
 98             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 99             {
100                 if(top==0)break;
101                 pre[u]=-1;
102                 u=edge[stack[--top]].s;
103             }
104             else//如果找到了继续运行
105             {
106                 stack[top++]=cur[u];
107                 u=edge[cur[u]].t;
108             }
109         }
110     }
111     return flow;
112 }
113 int main()
114 {
115     while(~scanf("%d%d",&n,&m))
116     {
117         int si,ni,ti;
118         int sum=0;
119         memset(head,-1,sizeof(head));
120         ent=0;
121         s=0;t=3*n+1;
122         int tot=0;
123         for(int i=1;i<=n;i++)
124         {
125             scanf("%d%d%d%d",&cust[i].start,&ni,&cust[i].last,&ti);
126             cust[i].stay=ni*ti;
127             sum+=cust[i].stay;
128             time[tot++]=cust[i].start;
129             time[tot++]=cust[i].last;
130         }
131         sort(time,time+2*n);
132         for(int i=1;i<=n;i++)
133             add(s,i,cust[i].stay);//cout<<"road:"<<i<<" start:"<<cust[i].start<<" last:"<<cust[i].last<<endl;}
134         //cout<<"time[0]:"<<time[0]<<endl;
135         for(int i=1;i<2*n;i++)
136         {
137             //cout<<"time["<<i<<"]:"<<time[i]<<endl;
138             if(time[i]==time[i-1])continue;
139             for(int j=1;j<=n;j++)
140             {
141                 if(cust[j].start<=time[i-1]&&cust[j].last>=time[i])
142                     add(j,n+i,m*(time[i]-time[i-1]));
143             }
144             add(n+i,t,m*(time[i]-time[i-1]));
145         }
146         //for(int i=0;i<ent;i++)
147             //if(edge[i].f)cout<<"s:"<<edge[i].s<<" t:"<<edge[i].t<<" f:"<<edge[i].f<<endl;
148         if(sum==dinic(s,t))
149             printf("Yes\n");
150         else printf("No\n");
151     }
152     return 0;
153 }

必威 9必威 10

View Code

 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 }

2.poj3469

View Code

题意:一高对核查处理器,给你基本上单任务,分别让有每个任务在首先独按以及次个核上运行的耗费。后面的m行输入是受有些许个任务在少单不同核上运行需要交的附加吃。

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

筑图:把每个任务作为节点,在超级源点与任务之中的连一漫长边,其容量也被任务在核1上运行的吃,在该任务节点和超级汇点之间并一长长的边,容量也该任务在核2上运行的吃。

  题意:有m个人,t时刻后会见下雨。地上发n把伞,每把伞只能一个人数因此。给出人和雨伞的坐标,以及人之速,问于下雨前,最多克发出微微个人拿到伞?

          
在职责中连接无向度,容量为有限个任务不以相同核及运行的附加吃。

  思路:人看做x集,伞作为y集,如果人会到达伞的位置,把欠人数之号与该伞的数码连线。之后请最好可怜匹配。Hopcroft-Carp算法。

当下题巧就正好于即时词:在职责中连续无为无尽,容量也片单任务不在同核及运行的额外吃。表示未是可怜理解,如果有大神在跪求带自己假装逼带本人飞n(*≧▽≦*)n

必威 11必威 12

代码:

  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 }

必威 13必威 14

View Code

  1 #include<iostream>
  2 #include<queue>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<climits>
  6 #define MAXE 1641000
  7 #define MAXP 20010
  8 #define Max(a,b) a>b?a:b
  9 #define Min(a,b) a<b?a:b
 10 using namespace std;
 11 struct Edge
 12 {
 13     int s,t,f,next;
 14 } edge[MAXE];
 15 int head[MAXP];
 16 int cur[MAXP];
 17 int pre[MAXP];
 18 int stack[MAXE];
 19 int used[MAXP];
 20 int ent;
 21 int n,m,s,t;
 22 int num;
 23 void add(int start,int last,int f)
 24 {
 25     edge[ent].s=start;
 26     edge[ent].t=last;
 27     edge[ent].f=f;
 28     edge[ent].next=head[start];
 29     head[start]=ent++;
 30     edge[ent].s=last;
 31     edge[ent].t=start;
 32     edge[ent].f=0;
 33     edge[ent].next=head[last];
 34     head[last]=ent++;
 35 }
 36 bool bfs(int S,int T)
 37 {
 38     memset(pre,-1,sizeof(pre));
 39     pre[S]=0;
 40     queue<int>q;
 41     q.push(S);
 42     while(!q.empty())
 43     {
 44         int temp=q.front();
 45         q.pop();
 46         for(int i=head[temp]; i!=-1; i=edge[i].next)
 47         {
 48             int temp2=edge[i].t;
 49             if(pre[temp2]==-1&&edge[i].f)
 50             {
 51                 pre[temp2]=pre[temp]+1;
 52                 q.push(temp2);
 53             }
 54         }
 55     }
 56     return pre[T]!=-1;
 57 }
 58 int dinic(int start,int last)
 59 {
 60     int flow=0,now;
 61     while(bfs(start,last))
 62     {
 63         int top=0;
 64         memcpy(cur,head,sizeof(head));
 65         int u=start;
 66         while(1)
 67         {
 68             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 69             {
 70                 int minn=INT_MAX;
 71                 for(int i=0; i<top; i++)
 72                 {
 73                     if(minn>edge[stack[i]].f)
 74                     {
 75                         minn=edge[stack[i]].f;
 76                         now=i;
 77                     }
 78                 }
 79                 for(int i=0;i<top;i++)
 80                 {
 81                     edge[stack[i]].f-=minn;
 82                     edge[stack[i]^1].f+=minn;
 83                 }
 84                 flow+=minn;
 85                 top=now;
 86                 u=edge[stack[top]].s;
 87             }
 88             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 89                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 90                     break;
 91             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 92             {
 93                 if(top==0)break;
 94                 pre[u]=-1;
 95                 u=edge[stack[--top]].s;
 96             }
 97             else//如果找到了继续运行
 98             {
 99                 stack[top++]=cur[u];
100                 u=edge[cur[u]].t;
101             }
102         }
103     }
104     return flow;
105 }
106 int main()
107 {
108     while(~scanf("%d%d",&n,&m))
109     {
110         memset(head,-1,sizeof(head));
111         ent=0;
112         s=0;t=n+1;
113         int cost1,cost2;
114         for(int i=1;i<=n;i++)
115         {
116             scanf("%d%d",&cost1,&cost2);
117             add(s,i,cost1);
118             add(i,t,cost2);
119         }
120         int u,v,cost;
121         for(int i=1;i<=m;i++)
122         {
123             scanf("%d%d%d",&u,&v,&cost);
124             add(u,v,cost);
125             add(v,u,cost);
126         }
127         printf("%d\n",dinic(s,t));
128     }
129     return 0;
130 }

6、hdu 4185 Oil Skimming

View Code

  题意:给出同布置图,每相邻两独油田可以起一起沟渠。问尽充分渠道的数额。

 3.hdu3061

  思路:给各一个油田编号。油田既当x集,又作为y集,如果少片油田相邻,则连线。之后请最好充分匹配。

中文题,思路就是是无比深且闭合图(妈蛋我还直接从未看下,没活了,不管什么算法不刷题果然都特么不行呀/(ㄒoㄒ)/~~)

必威 15必威 16

附带一点自身对最特别且闭合图的知情:如果连边2->3流量吧无根本,代表的无是2牵制3,而是3携制2,即要形成了3才能够去就2,而不是水到渠成了2才会去完3

  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

必威 17必威 18

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

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 250000
  8 #define MAXP 500
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Cust
 17 {
 18     int start,last,stay;
 19 }cust[MAXP];
 20 int head[MAXP];
 21 int time[MAXP*2];
 22 int stay[MAXP];
 23 int cur[MAXP];
 24 int pre[MAXP];
 25 int stack[MAXE];
 26 int used[MAXP];
 27 int ent;
 28 int n,m,s,t;
 29 int num;
 30 void add(int start,int last,int f)
 31 {
 32     edge[ent].s=start;
 33     edge[ent].t=last;
 34     edge[ent].f=f;
 35     edge[ent].next=head[start];
 36     head[start]=ent++;
 37     edge[ent].s=last;
 38     edge[ent].t=start;
 39     edge[ent].f=0;
 40     edge[ent].next=head[last];
 41     head[last]=ent++;
 42 }
 43 bool bfs(int S,int T)
 44 {
 45     memset(pre,-1,sizeof(pre));
 46     pre[S]=0;
 47     queue<int>q;
 48     q.push(S);
 49     while(!q.empty())
 50     {
 51         int temp=q.front();
 52         q.pop();
 53         for(int i=head[temp]; i!=-1; i=edge[i].next)
 54         {
 55             int temp2=edge[i].t;
 56             if(pre[temp2]==-1&&edge[i].f)
 57             {
 58                 pre[temp2]=pre[temp]+1;
 59                 q.push(temp2);
 60             }
 61         }
 62     }
 63     return pre[T]!=-1;
 64 }
 65 int dinic(int start,int last)
 66 {
 67     int flow=0,now;
 68     while(bfs(start,last))
 69     {
 70         int top=0;
 71         memcpy(cur,head,sizeof(head));
 72         int u=start;
 73         while(1)
 74         {
 75             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 76             {
 77                 int minn=INT_MAX;
 78                 for(int i=0; i<top; i++)
 79                 {
 80                     if(minn>edge[stack[i]].f)
 81                     {
 82                         minn=edge[stack[i]].f;
 83                         now=i;
 84                     }
 85                 }
 86                 for(int i=0;i<top;i++)
 87                 {
 88                     edge[stack[i]].f-=minn;
 89                     edge[stack[i]^1].f+=minn;
 90                 }
 91                 flow+=minn;
 92                 top=now;
 93                 u=edge[stack[top]].s;
 94             }
 95             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 96                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 97                     break;
 98             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 99             {
100                 if(top==0)break;
101                 pre[u]=-1;
102                 u=edge[stack[--top]].s;
103             }
104             else//如果找到了继续运行
105             {
106                 stack[top++]=cur[u];
107                 u=edge[cur[u]].t;
108             }
109         }
110     }
111     return flow;
112 }
113 int main()
114 {
115     while(~scanf("%d%d",&n,&m))
116     {
117         memset(head,-1,sizeof(head));
118         ent=0;s=0;t=n+1;
119         int cost,sum=0;
120         for(int i=1;i<=n;i++)
121         {
122             scanf("%d",&cost);
123             if(cost>0)
124             {
125                 add(s,i,cost);
126                 sum+=cost;
127             }
128             else
129                 add(i,t,-cost);
130         }
131         for(int i=1;i<=m;i++)
132         {
133             int u,v;
134             scanf("%d%d",&u,&v);
135             add(u,v,INT_MAX);
136         }
137         printf("%d\n",sum-dinic(s,t));
138     }
139     return 0;
140 }

  题意:每个天线最多只能埋好所于的格子和一个邻近的位置(可以是都市啊得以是空地)。问尽少之天线数目。

View Code

  思路:把每个城市拆成稀沾,让那个既属于x集又属y集,然后把附近之都连线。计算最老匹配,然后用总都数-最深匹配数即得最为小路径覆盖(用最为少的界限,覆盖所有终端。每个终端初始各起一样长达边,如果少单点连,则以使答案中的各个条边都未克交于相同一点,所以若减弱1.尾声就是减去太老匹配数).

 

必威 19必威 20

4.hdu1733&&poj3057

  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 }

hdu1733题意:

View Code

来一个近似于迷宫搜索的觊觎,‘.’代表的凡随便人之路途,’X’代表有人的点,’#’代表者点不足通过,’@’代表门口。每个位置各一样秒钟才会站一个人数,每个位置及上下左右点的日子吧1,问你富有人能不能够下,能出输出所有人数都出来的顶小时间,否则输出-1.

8、hdu 1054 Strategic Game POJ1463

建图:

  题意:有同蔸树,现在待以树上结点的职务放士兵,每个士兵能够防守和那所当交点相连接的边。问尽少放多少兵,能够防守所有的无尽。

1.拆点,对于第d天,每个点就于拆为d+1独点,下标代号成等差数列 公差n*m.

  思路:每个点既属于x集,又属于y集,两点次如果发生限度则连线。计算最特别匹配。(如果a和b、c、d相连,那么要选a和b相连的即条边,则未可知重新选择a点,也便非克重复择同a连接的度)

2.苗头的下,s向第0天之n*m中是人数之触发并条权值为1底限度。

必威 21必威 22

3.而后由小至大枚举每天,假要第t上,那么对t-1龙之接触好往周围扩展,或未动,向对诺于第t龙新加底点连条权为1底度,然后针对第t上之n*m点,如果是讲话则为汇点连条权值为1底底限,然后起源点到汇点做网络流,如果ans等于人,则break,return
t。

  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 }

4.对此没有消除的动静,先dfs判断是否有解处理的。

View Code

ps:我领到一个注意事项,虽然一般从不傻逼到一定水平不见面冒出这种题材/(ㄒoㄒ)/,那即便是:i,j对诺之职是(i-1)*m+j而不是(i-1)*n+j,因为这个自己wa了20破,花了片上/(ㄒoㄒ)/

9、hdu 1151/poj 1422 Air Raid

代码:

  题意:有相同发生向无环图,如果当一个结点放士兵,那么该也克防守和那个不断的起往无尽能到的结点。问尽少要多少守卫能够防守所有结点。

必威 23必威 24

  思路:同齐平等书,不过注意有向边。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 2000000
  8 #define MAXP 200024
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Point
 17 {
 18     int x,y;
 19 };
 20 int head[MAXP];
 21 int cur[MAXP];
 22 int pre[MAXP];
 23 int stack[MAXE];
 24 int ent;
 25 int n,m,s,t;
 26 int num;
 27 char map[18][18];
 28 bool can[18][18];
 29 bool visit[18][18];
 30 int dx[5]= {0,0,1,-1,0};
 31 int dy[5]= {1,-1,0,0,0};
 32 bool IN(int x,int y)
 33 {
 34     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='#'&&!visit[x][y];
 35 }
 36 bool BFS(int x,int y)
 37 {
 38     memset(visit,false,sizeof(visit));
 39     Point temp,temp1;
 40     temp.x=x;
 41     temp.y=y;
 42     queue<Point>q;
 43     q.push(temp);
 44     while(!q.empty())
 45     {
 46         temp=q.front();
 47         q.pop();
 48         for(int i=0; i<4; i++)
 49         {
 50             temp1.x=temp.x+dx[i];
 51             temp1.y=temp.y+dy[i];
 52             if(can[temp1.x][temp1.y]||map[temp1.x][temp1.y]=='@')
 53             {
 54                 can[x][y]=can[temp1.x][temp1.y]=true;
 55                 return true;
 56             }
 57             if(IN(temp1.x,temp1.y))
 58             {
 59                 q.push(temp1);
 60                 visit[temp1.x][temp.y]=true;
 61             }
 62         }
 63     }
 64     return false;
 65 }
 66 void add(int start,int last,int f)
 67 {
 68     edge[ent].s=start;
 69     edge[ent].t=last;
 70     edge[ent].f=f;
 71     edge[ent].next=head[start];
 72     head[start]=ent++;
 73     edge[ent].s=last;
 74     edge[ent].t=start;
 75     edge[ent].f=0;
 76     edge[ent].next=head[last];
 77     head[last]=ent++;
 78 }
 79 bool bfs(int S,int T)
 80 {
 81     memset(pre,-1,sizeof(pre));
 82     pre[S]=0;
 83     queue<int>q;
 84     q.push(S);
 85     while(!q.empty())
 86     {
 87         int temp=q.front();
 88         q.pop();
 89         for(int i=head[temp]; i!=-1; i=edge[i].next)
 90         {
 91             int temp2=edge[i].t;
 92             if(pre[temp2]==-1&&edge[i].f)
 93             {
 94                 pre[temp2]=pre[temp]+1;
 95                 q.push(temp2);
 96             }
 97         }
 98     }
 99     return pre[T]!=-1;
100 }
101 int dinic(int start,int last)
102 {
103     int flow=0,now;
104     while(bfs(start,last))
105     {
106         int top=0;
107         memcpy(cur,head,sizeof(head));
108         int u=start;
109         while(1)
110         {
111             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
112             {
113                 int minn=INT_MAX;
114                 for(int i=0; i<top; i++)
115                 {
116                     if(minn>edge[stack[i]].f)
117                     {
118                         minn=edge[stack[i]].f;
119                         now=i;
120                     }
121                 }
122                 for(int i=0; i<top; i++)
123                 {
124                     edge[stack[i]].f-=minn;
125                     edge[stack[i]^1].f+=minn;
126                 }
127                 flow+=minn;
128                 top=now;
129                 u=edge[stack[top]].s;
130             }
131             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
132                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
133                     break;
134             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
135             {
136                 if(top==0)break;
137                 pre[u]=-1;
138                 u=edge[stack[--top]].s;
139             }
140             else//如果找到了继续运行
141             {
142                 stack[top++]=cur[u];
143                 u=edge[cur[u]].t;
144             }
145         }
146     }
147     return flow;
148 }
149 bool in(int x,int y)
150 {
151     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='#';
152 }
153 int main()
154 {
155     while(~scanf("%d%d",&n,&m))
156     {
157         num=0;
158         memset(can,false,sizeof(can));
159         for(int i=1;i<=n;i++)
160         {
161             scanf("%s",map[i]+1);
162         }
163         bool ok=true;
164         for(int i=1; i<=n; i++)
165         {
166             for(int j=1; j<=m; j++)
167             {
168                 if(map[i][j]=='X')
169                 {
170                     num++;
171                     if(!BFS(i,j))
172                     {
173                         ok=false;
174                     }
175                 }
176             }
177         }
178         if(num==0)
179         {
180             cout<<0<<endl;
181             continue;
182         }
183         if(!ok)
184         {
185             printf("-1\n");
186         }
187         else
188         {
189             ent=0;
190             memset(head,-1,sizeof(head));
191             s=0;t=200023;
192             for(int mid=1;; mid++)
193             {
194                 int time=mid;
195                 for(int i=1; i<=n; i++)
196                 {
197                     for(int j=1; j<=m; j++)
198                     {
199                         if(map[i][j]=='#')continue;
200                         if(map[i][j]=='@')
201                         {
202                             add(time*2*n*m+(i-1)*m+j,t,1);
203                             continue;
204                         }
205                         add((time-1)*2*m*n+(i-1)*m+j,(time*2-1)*n*m+(i-1)*m+j,1);
206                         if(time==1&&map[i][j]=='X')
207                             add(s,(i-1)*m+j,1);
208                         for(int k=0; k<5; k++)
209                         {
210                             int x=i+dx[k];
211                             int y=j+dy[k];
212                             if(in(x,y))
213                             {
214                                 add((time*2-1)*n*m+(i-1)*m+j,time*2*n*m+(x-1)*m+y,1);
215                             }
216                         }
217                     }
218                 }
219                 int temp=dinic(s,t);
220                 if(temp==num)
221                 {
222                     cout<<mid<<endl;
223                     break;
224                 }
225                 num-=temp;
226             }
227         }
228     }
229     return 0;
230 }

必威 25必威 26

View Code

 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 }

poj3057:

View Code

中心等同,两独例外:1.开端时每个空格位置还来一个人口,2:后来除派的外别的地方都得发众多口,但是出来的言语一样不良只能出去一个人数。

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

代码:

   题意:同齐亦然开近似,不过允许两单机器人搜索与一个极端。

必威 27必威 28

  思路:用Folyd,把少单间接相连的顶峰直接连上。之后思路及达标亦然挥毫类似。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 1000000
  8 #define MAXP 20000
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Point
 17 {
 18     int x,y;
 19 };
 20 int head[MAXP];
 21 int cur[MAXP];
 22 int pre[MAXP];
 23 int stack[MAXE];
 24 int ent;
 25 int n,m,s,t;
 26 int num;
 27 char map[14][14];
 28 bool can[14][14];
 29 bool visit[14][14];
 30 int dx[5]= {0,0,1,-1,0};
 31 int dy[5]= {1,-1,0,0,0};
 32 bool IN(int x,int y)
 33 {
 34     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='X'&&!visit[x][y];
 35 }
 36 bool BFS(int x,int y)
 37 {
 38     memset(visit,false,sizeof(visit));
 39     Point temp,temp1;
 40     temp.x=x;
 41     temp.y=y;
 42     visit[x][y]=true;
 43     queue<Point>q;
 44     q.push(temp);
 45     while(!q.empty())
 46     {
 47         temp=q.front();
 48         q.pop();
 49         for(int i=0; i<4; i++)
 50         {
 51             temp1.x=temp.x+dx[i];
 52             temp1.y=temp.y+dy[i];
 53             if(can[temp1.x][temp1.y]||map[temp1.x][temp1.y]=='D')
 54             {
 55                 can[x][y]=can[temp1.x][temp1.y]=true;
 56                 return true;
 57             }
 58             if(IN(temp1.x,temp1.y))
 59             {
 60                 q.push(temp1);
 61                 visit[temp1.x][temp.y]=true;
 62             }
 63         }
 64     }
 65     return false;
 66 }
 67 void add(int start,int last,int f)
 68 {
 69     edge[ent].s=start;
 70     edge[ent].t=last;
 71     edge[ent].f=f;
 72     edge[ent].next=head[start];
 73     head[start]=ent++;
 74     edge[ent].s=last;
 75     edge[ent].t=start;
 76     edge[ent].f=0;
 77     edge[ent].next=head[last];
 78     head[last]=ent++;
 79 }
 80 bool bfs(int S,int T)
 81 {
 82     memset(pre,-1,sizeof(pre));
 83     pre[S]=0;
 84     queue<int>q;
 85     q.push(S);
 86     while(!q.empty())
 87     {
 88         int temp=q.front();
 89         q.pop();
 90         for(int i=head[temp]; i!=-1; i=edge[i].next)
 91         {
 92             int temp2=edge[i].t;
 93             if(pre[temp2]==-1&&edge[i].f)
 94             {
 95                 pre[temp2]=pre[temp]+1;
 96                 q.push(temp2);
 97             }
 98         }
 99     }
100     return pre[T]!=-1;
101 }
102 int dinic(int start,int last)
103 {
104     int flow=0,now;
105     while(bfs(start,last))
106     {
107         int top=0;
108         memcpy(cur,head,sizeof(head));
109         int u=start;
110         while(1)
111         {
112             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
113             {
114                 int minn=INT_MAX;
115                 for(int i=0; i<top; i++)
116                 {
117                     if(minn>edge[stack[i]].f)
118                     {
119                         minn=edge[stack[i]].f;
120                         now=i;
121                     }
122                 }
123                 for(int i=0; i<top; i++)
124                 {
125                     edge[stack[i]].f-=minn;
126                     edge[stack[i]^1].f+=minn;
127                 }
128                 flow+=minn;
129                 top=now;
130                 u=edge[stack[top]].s;
131             }
132             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
133                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
134                     break;
135             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
136             {
137                 if(top==0)break;
138                 pre[u]=-1;
139                 u=edge[stack[--top]].s;
140             }
141             else//如果找到了继续运行
142             {
143                 stack[top++]=cur[u];
144                 u=edge[cur[u]].t;
145             }
146         }
147     }
148     return flow;
149 }
150 bool in(int x,int y)
151 {
152     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='X';
153 }
154 int main()
155 {
156     int cas;
157     cin>>cas;
158     while(cas--)
159     {
160         scanf("%d%d",&n,&m);
161         num=0;
162         memset(can,false,sizeof(can));
163         for(int i=1; i<=n; i++)
164             scanf("%s",map[i]+1);
165         bool ok=true;
166         for(int i=1; i<=n; i++)
167         {
168             for(int j=1; j<=m; j++)
169             {
170                 if(map[i][j]=='.')
171                 {
172                     num++;
173                     if(!BFS(i,j))
174                     {
175                         ok=false;
176                     }
177                 }
178                 /*if(map[i][j]=='D')
179                 {
180                     int oks=0;
181                     for(int k=0;k<4;k++)
182                     {
183                         int x=i+dx[k];
184                         int y=j+dy[k];
185                         if(x<1||x>n||y<1||y>m)continue;
186                         if(map[x][y]=='.')
187                             oks++;
188                     }
189                     if(!oks)
190                         map[i][j]='X';
191                 }*/
192             }
193         }
194         if(num==0)
195         {
196             cout<<0<<endl;
197             continue;
198         }
199         if(!ok)
200         {
201             printf("impossible\n");
202         }
203         else
204         {
205             memset(head,-1,sizeof(head));
206             ent=0;
207             s=0;
208             t=19999;
209             for(int mid=1;; mid++)
210             {
211                 //s=0;
212                 //t=(mid+1)*n*m+1;
213                 int time=mid;
214                 for(int i=1; i<=n; i++)
215                 {
216                     for(int j=1; j<=m; j++)
217                     {
218                         if(map[i][j]=='X')continue;
219                         if(time==1&&map[i][j]=='.')
220                             add(s,(i-1)*m+j,1);
221                         if(map[i][j]=='D')
222                         {
223                             add(time*n*m+(i-1)*m+j,t,1);
224                             continue;
225                         }
226                         for(int k=0; k<5; k++)
227                         {
228                             int x=i+dx[k];
229                             int y=j+dy[k];
230                             if(in(x,y))
231                             {
232                                 add((time-1)*n*m+(i-1)*m+j,time*n*m+(x-1)*m+y,INT_MAX);
233                             }
234                         }
235                     }
236                 }
237                 int temp=dinic(s,t);
238                 if(temp==num)
239                 {
240                     cout<<mid<<endl;
241                     break;
242                 }
243                 num-=temp;
244             }
245         }
246     }
247     return 0;
248 }

必威 29必威 30

View Code

  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 }

 

View Code

 

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

5.poj2396  有上下界有源汇的可行流

  题意:每个孩子还出喜欢的以及免喜的某个仅狗或有才猫(如果喜欢狗,则非喜欢猫,反之亦然)。现在,动物园管理者想使淘汰部分狗和猫,使得最后高兴之男女最多(只有爱的那就,不欣赏的那么不过为淘汰)。

题意:

  思路:如果一个人口喜欢的某某就狗要某就猫正是其余一个总人口未喜的某个特狗或某独自猫,则两者是矛盾,将矛盾的星星点点个人口连线。最后求出的顶酷匹配数位=为要淘汰的动物之数码,剩下的口里还未曾互相矛盾的地方。即求最可怜独立集。

题目大意:有一个n*m的矩阵,每个岗位(i,j)都来一个价,接下去输入n个数,每个数代表矩阵对应行的和,接下输入m个数,每个数代表针对应列的跟。接下来起Q个操作,每个操作输入i
j c val。

必威 31必威 32

1、当c为’>’: 表示第i行j列的数值要高于val。(实际下级要如为val+1)

  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 }

2、当c为'<‘: 表示第i行j列的数值要自愧不如val。(实际上界要要为val-1)

View Code

3、当c为’=’: 表示第i行j列的数值要对等val。

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

于您请是否留存满足要求的矩阵,有则输出对应之矩阵,无则输出”impossible”。

  题意:有n个人,有m个群组。每个人都起多少足进入的群组。现在用把每个人分配到一个群组,并且分配殆尽晚,保证人数最多之良群组的人最为少。

留神:i=0||j=0表示那一行||那同样排列的各一个频繁都符合要求而休是所有数的跟符合要求,妈的为坑了一样龙有木有,直接哭晕在洗手间,真的抓狂了,英语差简直没有存路呀

  思路:①变网络流。建立一个分外源点和汇点。限制每个群组的极端酷容量,源点与每个人不断,每条边容量为1;人同那个能加入的群组连边,容量为1;每个群组和汇点连边,容量也即所枚举的界定容量。如果以时下限定容量下,最充分流为n,则连续尝试缩小限制,否则放大限制。(二分操作)(Dinic算法,借鉴模板)

解题思路:

必威 33必威 34

增设一源点s和相同集合点d,源点s和每行的意味虚拟节点row[i]连发,权值为该行的权值总和,每列的表示虚拟节点和汇点d相连,权值为该列的权值总和,行连接列代表节点(i,j)即i行j列,它的容量达下界根据题目来规定。

  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 }

           
连接一长达附加边(d,s)容量也无根本,剩下的操作和无源汇有上下界的可行流一样。

View Code

小心:上下界不克出一个尽管加同蹩脚这样见面出错的,一定要拿装有的操作全部行定然后当确定最终的上下界,不然也是碰头wa的

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

代码:

  题意:给出牛和机器内部的相距(二维矩阵代表,如果i==j,值为0;如果不能到达,值也输入为0),现在,在担保拥有牛还能抵挤奶机械下,使得移动得最丰富之牛之运动的离开最小。

必威 35必威 36

  思路:①预先用Floyd算有个别点滴里面极短距离。然后换网络流,限制最老距。建立一个分外源点与汇点,源点和每头牛相连,容量也1;牛和机具中的极致短距离小于等于限制距离则连线,容量也1;机器及汇点连线,容量为1.每次二私分限制最短距离。(Dinic算法,和直达一个富有修改,上一个错,不太明了)

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 5000000
  8 #define MAXP 4400
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 int head[MAXP];
 17 int flow[MAXP];
 18 int degree[MAXP];
 19 int cur[MAXP];
 20 int pre[MAXP];
 21 int stack[MAXE];
 22 int maxn[MAXP];
 23 int minn[MAXP];
 24 int ent;
 25 int n,m,s,t,supers,supert;
 26 int num;
 27 void add(int start,int last,int f)
 28 {
 29     edge[ent].s=start;
 30     edge[ent].t=last;
 31     edge[ent].f=f;
 32     edge[ent].next=head[start];
 33     head[start]=ent++;
 34     edge[ent].s=last;
 35     edge[ent].t=start;
 36     edge[ent].f=0;
 37     edge[ent].next=head[last];
 38     head[last]=ent++;
 39 }
 40 bool bfs(int S,int T)
 41 {
 42     memset(pre,-1,sizeof(pre));
 43     pre[S]=0;
 44     queue<int>q;
 45     q.push(S);
 46     while(!q.empty())
 47     {
 48         int temp=q.front();
 49         q.pop();
 50         for(int i=head[temp]; i!=-1; i=edge[i].next)
 51         {
 52             int temp2=edge[i].t;
 53             if(pre[temp2]==-1&&edge[i].f)
 54             {
 55                 pre[temp2]=pre[temp]+1;
 56                 q.push(temp2);
 57             }
 58         }
 59     }
 60     return pre[T]!=-1;
 61 }
 62 int dinic(int start,int last)
 63 {
 64     int flow=0,now;
 65     while(bfs(start,last))
 66     {
 67         int top=0;
 68         memcpy(cur,head,sizeof(head));
 69         int u=start;
 70         while(1)
 71         {
 72             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 73             {
 74                 int minn=INT_MAX;
 75                 for(int i=0; i<top; i++)
 76                 {
 77                     if(minn>edge[stack[i]].f)
 78                     {
 79                         minn=edge[stack[i]].f;
 80                         now=i;
 81                     }
 82                 }
 83                 for(int i=0; i<top; i++)
 84                 {
 85                     edge[stack[i]].f-=minn;
 86                     edge[stack[i]^1].f+=minn;
 87                 }
 88                 flow+=minn;
 89                 top=now;
 90                 u=edge[stack[top]].s;
 91             }
 92             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 93                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 94                     break;
 95             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 96             {
 97                 if(top==0)break;
 98                 pre[u]=-1;
 99                 u=edge[stack[--top]].s;
100             }
101             else//如果找到了继续运行
102             {
103                 stack[top++]=cur[u];
104                 u=edge[cur[u]].t;
105             }
106         }
107     }
108     return flow;
109 }
110 int main()
111 {
112     int cas;
113     cin>>cas;
114     while(cas--)
115     {
116         scanf("%d%d",&n,&m);
117         memset(head,-1,sizeof(head));
118         memset(flow,0,sizeof(flow));
119         memset(maxn,-1,sizeof(maxn));
120         memset(minn,0,sizeof(minn));
121         ent=0;
122         int ok=1;
123         s=0;
124         t=n+m+n*m+1;
125         supers=t+1;
126         supert=t+2;
127         int hang[200+1];
128         int lie[200+1];
129         int sumhang=0,sumlie=0;
130         memset(degree,0,sizeof(degree));
131         int temp;
132         for(int i=1; i<=n; i++)
133         {
134             scanf("%d",&temp);
135             if(temp<0)ok=0;
136             hang[i]=temp;
137             sumhang+=temp;
138             degree[i]+=temp;
139             degree[s]-=temp;
140             add(s,i,0);
141         }
142         for(int i=n+1; i<=n+m; i++)
143         {
144             scanf("%d",&temp);
145             if(temp<0)ok=0;
146             lie[i-n]=temp;
147             sumlie+=temp;
148             degree[i]-=temp;
149             degree[t]+=temp;
150             add(i,t,0);
151         }
152         add(t,s,INT_MAX);
153         if(sumhang!=sumlie)ok=0;
154         scanf("%d",&num);
155         int u,v,sum;
156         char chara;
157         for(int i=1; i<=num; i++)
158         {
159             cin>>u>>v>>chara>>sum;
160             int s1=u,t1=u;
161             int s2=v,t2=v;
162             if(u==0)s1=1,t1=n;
163             if(v==0)s2=1,t2=m;
164             for(u=s1;u<=t1;u++)
165             for(v=s2;v<=t2;v++)
166             {
167                 if(chara=='<')
168                 {
169                     if(sum<=0)
170                         ok=0;
171                     else
172                     {
173                         if(maxn[(u-1)*m+v]==-1)
174                             maxn[(u-1)*m+v]=sum-1;
175                         else maxn[(u-1)*m+v]=Min(maxn[(u-1)*m+v],sum-1);
176                     }
177                 }
178                 else if(chara=='=')
179                 {
180                     if(sum<0)ok=0;
181                     if(maxn[(u-1)*m+v]!=-1&&maxn[(u-1)*m+v]<sum)ok=0;
182                     if(minn[(u-1)*m+v]>sum)ok=0;
183                     maxn[(u-1)*m+v]=sum;
184                     minn[(u-1)*m+v]=sum;
185                 }
186                 else if(chara=='>')
187                 {
188                     if(sum<0)continue;
189                     if(sum>=hang[u])
190                         ok=0;
191                     else
192                     {
193                         minn[(u-1)*m+v]=Max(minn[(u-1)*m+v],sum+1);
194                     }
195                 }
196             }
197         }
198         for(int i=1; i<=n; i++)
199         {
200             if(!ok)break;
201             for(int j=1; j<=m; j++)
202             {
203                 if(maxn[(i-1)*m+j]==-1)maxn[(i-1)*m+j]=hang[i];
204                 if(maxn[(i-1)*m+j]<minn[(i-1)*m+j])
205                 {
206                     ok=0;
207                     break;
208                 }
209                 degree[i]-=minn[(i-1)*m+j];
210                 degree[j+n]+=minn[(i-1)*m+j];
211                 add(i,(i-1)*m+j+n+m,maxn[(i-1)*m+j]-minn[(i-1)*m+j]);
212                 add((i-1)*m+j+n+m,j+n,maxn[(i-1)*m+j]-minn[(i-1)*m+j]);
213                 flow[(i-1)*m+j]=minn[(i-1)*m+j];
214             }
215         }
216         if(!ok)
217         {
218             printf("IMPOSSIBLE\n");
219             if(cas)cout<<endl;
220             continue;
221         }
222         int all=0;
223         add(t,s,INT_MAX);
224         for(int i=s; i<=t; i++)
225         {
226             if(degree[i]<0)
227                 add(i,supert,-degree[i]);
228             else if(degree[i]>0)
229             {
230                 add(supers,i,degree[i]);
231                 all+=degree[i];
232             }
233         }
234         if(all==dinic(supers,supert))
235         {
236             for(int j=1; j<=n; j++)
237             {
238                 for(int i=head[j]; i!=-1; i=edge[i].next)
239                 {
240                     int aim=edge[i].t-n-m;
241                     if(aim>0&&aim<=n*m)
242                     {
243                         flow[aim]+=edge[i^1].f;
244                     }
245                 }
246             }
247             for(int i=1; i<=n; i++)
248             {
249                 for(int j=1; j<m; j++)
250                 {
251                     cout<<flow[(i-1)*m+j]<<" ";
252                 }
253                 cout<<flow[i*m]<<endl;
254             }
255         }
256         else cout<<"IMPOSSIBLE"<<endl;
257         if(cas)cout<<endl;
258     }
259     return 0;
260 }

必威 37必威 38

View Code

  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 }

 

View Code

hust1024
分层网络流(虽然这不是本人举行的首先道次私分枚举可行流的问题,但是于好会30分钟以内独立的无看题解a掉他还是深打动之,当然必然用了极度特别流动模板2333333333)

14、poj 3189 Steady Cow Assignment

题意:

  题意:有n头牛,b个畜棚。给出各头牛本好程度之预先级从很至小之牛圈编号,再吃来每个牛棚的容量。求某平等种分配下,在有牛中,其分割到的牛棚的顶特别优先级和太低优先级之异最小。

出n男n女,有m对儿女喜欢对方,每个男性的要么女之卓绝多与k个他无喜的阴之抑男的跳舞,然后是输入m对喜欢对方的孩子,然后为您请出最为多你被这样多口放几软针对,每次放对都未克吃一个人陪同曾经受她配了之食指。

  思路:①更换网络流,限制最可怜优先级和先期级的差,对于各一个限制,枚举其或的限制(比如来4独牛棚,限制差值为2,则恐的优先级范围也[1,3]或[2,4])。建立额外的源点和汇点,源点和每头牛相连,容量也1;牛以及该所划分优先级的范围外的牛圈连线,容量也1;每个牛棚和汇点相连,容量为牛棚各自的无比特别盛牛的数额。求最好要命流动。

思路:

必威 39必威 40

网络流,关键在于建图。

  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 }

             
 把男拆成稀只点,分别放置在片个集内,Xa和Xb,女性拆成稀只点,分别放置在Ya和Yb内。Xa到Xb连接一长达发出向度,权值为k,Yb到Ya连接一长条发出向无尽,权值为k。当boy喜欢girl时,Xa和Ya之间连接一漫漫对应的生向无尽权值为1,当boy不欣赏girl时,Xb和Yb连接一长达对应的出往度,权值为1。

View Code

             最后二分割枚举可行解ans,
超级源点到Xa的每个点总是一久有向度,权值为ans,Ya内之每个点和特等汇点连接一长有向度,权值也为ans。最后流啊流,最深流满足max_flow==n*ans时,继续次分叉,直到找到最好优解。(这当会比快,不过我是起小到大枚举的)

15、poj 3436 ACM Computer Factory

代码:

  题意:我们得装配p个配件。每台机器还来友好之克(满足进入限制条件(不能够产生怎样零件0、必须要产生怎么样零件1、哪些零件可有可无2)后才能够加工该半成品,加工后虽然会略零件具备1,有些零件没具备0)。同时,每台机械出独家的频率。问怎么设置加工流使得最后总效率最可怜。

必威 41必威 42

  思路:最要命流动。建立源点(什么零件都不曾)和汇点(什么零件都产生)。同时将各令机械分成两单点,一个输入,一个出口。只有满足输出输入关系之不等机器才能够连线,容量为INF。对于同一台机械,从输入连到输出,容量也效率。源点和满足输入条件的机器不断,容量为INF;机器输出后满足汇点要求的输出口和汇点相连,容量为INF,求平破最好特别流动。(Edmonds_Karp算法模板)

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 500000
  8 #define MAXP 450
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 int head[MAXP];
 17 int cur[MAXP];
 18 int pre[MAXP];
 19 int stack[MAXE];
 20 int ent;
 21 int n,m,k,s,t;
 22 int num;
 23 int dx[4]={0,0,1,-1};
 24 int dy[4]={1,-1,0,0};
 25 bool in(int x,int y)
 26 {
 27     return x>=1&&x<=n&&y>=1&&y<=m;
 28 }
 29 void add(int start,int last,int f)
 30 {
 31     edge[ent].s=start;
 32     edge[ent].t=last;
 33     edge[ent].f=f;
 34     edge[ent].next=head[start];
 35     head[start]=ent++;
 36     edge[ent].s=last;
 37     edge[ent].t=start;
 38     edge[ent].f=0;
 39     edge[ent].next=head[last];
 40     head[last]=ent++;
 41 }
 42 bool bfs(int S,int T)
 43 {
 44     memset(pre,-1,sizeof(pre));
 45     pre[S]=0;
 46     queue<int>q;
 47     q.push(S);
 48     while(!q.empty())
 49     {
 50         int temp=q.front();
 51         q.pop();
 52         for(int i=head[temp]; i!=-1; i=edge[i].next)
 53         {
 54             int temp2=edge[i].t;
 55             if(pre[temp2]==-1&&edge[i].f)
 56             {
 57                 pre[temp2]=pre[temp]+1;
 58                 q.push(temp2);
 59             }
 60         }
 61     }
 62     return pre[T]!=-1;
 63 }
 64 int dinic(int start,int last)
 65 {
 66     int flow=0,now;
 67     while(bfs(start,last))
 68     {
 69         int top=0;
 70         memcpy(cur,head,sizeof(head));
 71         int u=start;
 72         while(1)
 73         {
 74             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 75             {
 76                 int minn=INT_MAX;
 77                 for(int i=0; i<top; i++)
 78                 {
 79                     if(minn>edge[stack[i]].f)
 80                     {
 81                         minn=edge[stack[i]].f;
 82                         now=i;
 83                     }
 84                 }
 85                 for(int i=0; i<top; i++)
 86                 {
 87                     edge[stack[i]].f-=minn;
 88                     edge[stack[i]^1].f+=minn;
 89                 }
 90                 flow+=minn;
 91                 top=now;
 92                 u=edge[stack[top]].s;
 93             }
 94             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 95                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 96                     break;
 97             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 98             {
 99                 if(top==0)break;
100                 pre[u]=-1;
101                 u=edge[stack[--top]].s;
102             }
103             else//如果找到了继续运行
104             {
105                 stack[top++]=cur[u];
106                 u=edge[cur[u]].t;
107             }
108         }
109     }
110     return flow;
111 }
112 int main()
113 {
114     int cas;
115     int option[101][101];
116     scanf("%d",&cas);
117     while(cas--)
118     {
119         s=0;t=4*n+1;
120         memset(option,0,sizeof(option));
121         scanf("%d%d%d",&n,&m,&k);
122         int u,v;
123         memset(head,-1,sizeof(head));
124         ent=0;
125         for(int i=1;i<=m;i++)
126         {
127             scanf("%d%d",&u,&v);
128             option[u][v]=1;
129             add(u,v+n,1);
130         }
131         if(k!=0)
132         {
133             for(int i=1;i<=n;i++)
134             {
135                 add(i,2*n+i,k);
136                 add(3*n+i,n+i,k);
137             }
138             for(int i=1;i<=n;i++)
139             {
140                 for(int j=1;j<=n;j++)
141                 {
142                     if(!option[i][j])
143                     {
144                         add(2*n+i,3*n+j,1);
145                     }
146                 }
147             }
148         }
149         for(int i=1;i<=n+1;i++)
150         {
151             for(int j=1;j<=n;j++)
152             {
153                 add(s,j,1);
154                 add(j+n,t,1);
155             }
156             if(dinic(s,t)!=n)
157             {
158                 printf("%d\n",i-1);
159                 break;
160             }
161         }
162     }
163     return 0;
164 }

必威 43必威 44

View Code

  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 }

 poj1815 相当水的同一鸣不过可怜流动

View Code

题意加思路:

16、poj 3281 Dining

对问至少删掉几独点而得S、T不联通,可以将每个点拆成i、i’两单点并连一漫漫容量为1底i->i’的边,将其他涉及依次补全后请最好小割即可。

  题意:每头牛都产生投机爱的多个食品(编号)和喜爱的若干只饮料(编号)。但是每种食物要各种饮品都只好于同样匹牛。求饮料及食都能够获得的牛之尽充分只数。

   
但是这个题材要求输出字典序最小的结果,那么就是得依次枚举每个点,如果删掉这个点以后最好小割变多少了,那么即便印证这点是无比小割着之接触,将其除去,否则就是说称之点不是最为小割着之触及,将其过来。然后再度上面的操作就足以取字典序最小之排了。

  思路:最要命流动。建立源点和汇点。源点和每种食物相连,容量也1;把每头牛拆成稀单点(一个连食物<左牛>,一个总是饮料<右牛>),同一头牛的星星点点只点里连线,容量为1;把食物以及喜该食品的那头牛的左牛连线,容量也1;把右侧牛和该牛喜欢的饮品连线,容量为1;把有饮料连于汇点,容量为1.求一如既往糟顶特别流动。(Edmonds_Karp算法模板)

然就书为什么而大小便点未爱想清楚,我发生接触想法可是还要休明白怎么说,看来只能先记住了

必威 45必威 46

代码:

  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 }

必威 47必威 48

View Code

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 1000000
  8 #define MAXP 1024
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Edges
 17 {
 18     int t,next;
 19 } edges[MAXE];
 20 int head[MAXP];
 21 int isq[MAXP];
 22 int q[MAXP];
 23 int headedge[MAXP];
 24 int cur[MAXP];
 25 int pre[MAXP];
 26 int stack[MAXE];
 27 int ent,entedge;
 28 int n,a,b,s,t;
 29 void addedge(int start,int last)
 30 {
 31     edges[entedge].t=last;
 32     edges[entedge].next=headedge[start];
 33     headedge[start]=entedge++;
 34     edges[entedge].t=start;
 35     edges[entedge].next=headedge[last];
 36     headedge[last]=entedge++;
 37 }
 38 void add(int start,int last,int f)
 39 {
 40     edge[ent].s=start;
 41     edge[ent].t=last;
 42     edge[ent].f=f;
 43     edge[ent].next=head[start];
 44     head[start]=ent++;
 45     edge[ent].s=last;
 46     edge[ent].t=start;
 47     edge[ent].f=0;
 48     edge[ent].next=head[last];
 49     head[last]=ent++;
 50 }
 51 bool bfs(int S,int T)
 52 {
 53     memset(pre,-1,sizeof(pre));
 54     pre[S]=0;
 55     queue<int>q;
 56     q.push(S);
 57     while(!q.empty())
 58     {
 59         int temp=q.front();
 60         q.pop();
 61         for(int i=head[temp]; i!=-1; i=edge[i].next)
 62         {
 63             int temp2=edge[i].t;
 64             if(pre[temp2]==-1&&edge[i].f)
 65             {
 66                 pre[temp2]=pre[temp]+1;
 67                 q.push(temp2);
 68             }
 69         }
 70     }
 71     return pre[T]!=-1;
 72 }
 73 int dinic(int start,int last)
 74 {
 75     int flow=0,now;
 76     while(bfs(start,last))
 77     {
 78         int top=0;
 79         memcpy(cur,head,sizeof(head));
 80         int u=start;
 81         while(1)
 82         {
 83             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 84             {
 85                 int minn=INT_MAX;
 86                 for(int i=0; i<top; i++)
 87                 {
 88                     if(minn>edge[stack[i]].f)
 89                     {
 90                         minn=edge[stack[i]].f;
 91                         now=i;
 92                     }
 93                 }
 94                 for(int i=0; i<top; i++)
 95                 {
 96                     edge[stack[i]].f-=minn;
 97                     edge[stack[i]^1].f+=minn;
 98                 }
 99                 flow+=minn;
100                 top=now;
101                 u=edge[stack[top]].s;
102             }
103             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
104                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
105                     break;
106             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
107             {
108                 if(top==0)break;
109                 pre[u]=-1;
110                 u=edge[stack[--top]].s;
111             }
112             else//如果找到了继续运行
113             {
114                 stack[top++]=cur[u];
115                 u=edge[cur[u]].t;
116             }
117         }
118     }
119     return flow;
120 }
121 int main()
122 {
123     while(~scanf("%d%d%d",&n,&a,&b))
124     {
125         memset(head,-1,sizeof(head));
126         ent=0;
127         entedge=0;
128         memset(headedge,-1,sizeof(headedge));
129         memset(isq,0,sizeof(isq));
130         s=0;
131         t=2*n+1;
132         add(s,a,INT_MAX);
133         add(b,t,INT_MAX);
134         add(a,a+n,INT_MAX);
135         int temp;
136         int ok=0;
137         for(int i=1; i<=n; i++)
138         {
139             if(i!=a&&i!=b)
140                 add(i,i+n,1);
141             for(int j=1; j<=n; j++)
142             {
143                 scanf("%d",&temp);
144                 if(i==a&&j==b&&temp)ok=1;
145                 if(temp&&i<j)
146                 {
147                     add(i+n,j,1);
148                     add(j+n,i,1);
149                     addedge(i,j);
150                 }
151             }
152         }
153         temp=dinic(s,t);
154         if(ok)printf("NO ANSWER!");
155         else
156         {
157             printf("%d\n",temp);
158             if(temp)
159             {
160                 for(int i=1; i<=n; i++)
161                 {
162                     if(i==a||i==b)continue;
163                     memset(head,-1,sizeof(head));
164                     ent=0;
165                     add(s,a,INT_MAX);
166                     add(b,t,INT_MAX);
167                     add(a,a+n,INT_MAX);
168                     for(int j=1; j<=n; j++)
169                     {
170                         if(j==i||isq[j])continue;
171                         if(j!=a&&j!=b)add(j,j+n,1);
172                         for(int k=headedge[j]; k!=-1; k=edges[k].next)
173                         {
174                             int temps=edges[k].t;
175                             if(isq[temps]||temps==i)continue;
176                             add(j+n,temps,1);
177                         }
178                     }
179                     if(dinic(s,t)==temp-1)
180                     {
181                         isq[i]=1;
182                         temp-=1;
183                     }
184                     if(temp==0)break;
185                 }
186                 int tot=0;
187                 for(int i=1; i<=n; i++)
188                 {
189                     if(isq[i])q[tot++]=i;
190                 }
191                 for(int i=0; i<tot-1; i++)
192                     printf("%d ",q[i]);
193                 printf("%d\n",q[tot-1]);
194             }
195         }
196     }
197     return 0;
198 }

17、poj 1273 Drainage Ditches

View Code

  题意:有n个沟渠,m个结点(编号为1之也罢池,编号为m的吗溪流)。每个渠道都产生投机的尽要命流速,问于池塘到溪流的太老排水流速。

 poj1422最小路径覆盖

  思路:源点为池,汇点为溪流。根据沟渠的走向与流速建立图,求最好老流动。基础题。(Edmonds_Karp算法模板)

题意:

必威 49必威 50

    一个镇里所有的路程还是止为路且不会见构成回路。

 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 }

       派一些伞兵去大镇里,要达所有的街口,有局部或者没伞兵可以不失那些路口,只要其他人能不负众望这任务。每个在一个路口着陆了之空降兵可以顺着街去到另外路口。我们的天职是请求出执行任务之空降兵最少可以是稍微只。

View Code

思路:答案就是先行拆点次划分图,然后输出路口总数-最老流动,原因该就是每个匹配能抽一个求。

 18、poj 1087/uva 753 A Plug for
UNIX

代码:

  题意:房间外发n个插座板,有m个设备,有k种接口转换器,求最好少发微设备未能够插进插座。

 

  思路:最充分流动。关键是修建图必威。见代码注释。Dinic算法。

必威 51必威 52

必威 53必威 54

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 920000
  8 #define MAXP 100010
  9 using namespace std;
 10 struct Edge
 11 {
 12     int s,t,f,next;
 13 };
 14 class Dinic
 15 {
 16 public:
 17     Dinic();
 18     void insert(int st,int tt,int f);
 19     bool bfs();
 20     void init(int st,int tt);
 21     int dinic();
 22     void getCut();//获取割边S,先使用dinic获取最大流之后使用
 23     void dfs(int start);//在getCut中用来求出S
 24 private:
 25     int s,t;
 26     int ent;
 27     int flow;
 28     int *head;
 29     int *cur;
 30     int *pre;
 31     int *stack;
 32     Edge *edge;
 33     int *getS;
 34 };
 35 Dinic::Dinic()
 36 {
 37     head=new int[MAXP];
 38     cur=new int[MAXP];
 39     pre=new int[MAXP];
 40     stack=new int[MAXE];
 41     edge=new Edge[MAXE];
 42     getS=new int[MAXP];
 43 }
 44 void Dinic::init(int st,int tt)
 45 {
 46     memset(head,-1,sizeof(int)*MAXP);
 47     s=st;
 48     t=tt;
 49     ent=0;
 50     flow=0;
 51 }
 52 void Dinic::insert(int st,int tt,int f)
 53 {
 54     edge[ent].s=st;
 55     edge[ent].t=tt;
 56     edge[ent].f=f;
 57     edge[ent].next=head[st];
 58     head[st]=ent++;
 59     edge[ent].s=tt;
 60     edge[ent].t=st;
 61     edge[ent].f=0;
 62     edge[ent].next=head[tt];
 63     head[tt]=ent++;
 64 }
 65 bool Dinic::bfs()
 66 {
 67     memset(pre,-1,sizeof(int)*MAXP);
 68     pre[s]=0;
 69     queue<int>q;
 70     q.push(s);
 71     while(!q.empty())
 72     {
 73         int temp1=q.front();
 74         q.pop();
 75         for(int i=head[temp1]; i!=-1; i=edge[i].next)
 76         {
 77             int temp2=edge[i].t;
 78             if(pre[temp2]==-1&&edge[i].f)
 79             {
 80                 pre[temp2]=pre[temp1]+1;
 81                 q.push(temp2);
 82             }
 83         }
 84     }
 85     return pre[t]!=-1;
 86 }
 87 int Dinic::dinic()
 88 {
 89     int now;
 90     while(bfs())
 91     {
 92         int top=0;
 93         memcpy(cur,head,sizeof(int)*MAXP);
 94         int u=s;
 95         while(1)
 96         {
 97             if(u==t)
 98             {
 99                 int minn=INT_MAX;
100                 for(int i=0; i<top; i++)
101                 {
102                     if(minn>edge[stack[i]].f)
103                     {
104                         minn=edge[stack[i]].f;
105                         now=i;
106                     }
107                 }
108                 for(int i=0; i<top; i++)
109                 {
110                     edge[stack[i]].f-=minn;
111                     edge[stack[i]^1].f+=minn;
112                 }
113                 flow+=minn;
114                 top=now;
115                 u=edge[stack[top]].s;
116             }
117             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)
118                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
119                     break;
120             if(cur[u]==-1)
121             {
122                 if(top==0)break;
123                 pre[u]=-1;
124                 u=edge[stack[--top]].s;
125             }
126             else
127             {
128                 stack[top++]=cur[u];
129                 u=edge[cur[u]].t;
130             }
131         }
132     }
133     return flow;
134 }
135 void Dinic::getCut()
136 {
137     memset(getS,0,sizeof(int)*MAXP);
138     getS[s]=1;
139     dfs(s);
140     for(int i=0; i<MAXP; i++)
141     {
142         if(getS[i])
143             cout<<i<<" ";
144     }
145     cout<<endl;
146 }
147 void Dinic::dfs(int start)
148 {
149     for(int i=head[start]; i!=-1; i=edge[i].next)
150     {
151         if(edge[i].f)
152         {
153             int temp=edge[i].t;
154             if(!getS[temp])
155             {
156                 getS[temp];
157                 dfs(temp);
158             }
159         }
160     }
161 }
162 int main()
163 {
164     int cas,n,m,s,t,f;
165     Dinic *temp=new Dinic();
166     scanf("%d",&cas);
167     while(cas--)
168     {
169         scanf("%d%d",&n,&m);
170         temp->init(0,2*n+1);
171         for(int i=1; i<=n; i++)
172         {
173             temp->insert(0,i,1);
174             temp->insert(i+n,2*n+1,1);
175         }
176         for(int i=0; i<m; i++)
177         {
178             scanf("%d%d",&s,&t);
179             temp->insert(s,t+n,1);
180         }
181         cout<<(n-temp->dinic())<<endl;
182     }
183     delete temp;
184     return 0;
185 }
  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

View Code

 zoj3229

 

题意:

一个屌丝给m个女神拍,计划拍摄n天,每一样天屌丝给加的C个女神拍,每天拍数不可知跨越D张,而且吃每个女神i拍照发数量限制[Li,Ri],对于每个女神n天的留影到底跟非克少Gi,如果生解求屌丝最多能碰撞多少张照,并求每天被相应女神拍多少张照;否则输出-1。

自然就题我是未思量写博客的,毕竟这是自身以来学之,然而因一个坑,还是准备写一下,也许还能够让别人一点唤起呢

即时书之出口既未是出口屌丝每天被每个女神拍的多少,也无是要某天给某拍照数量是0就不出口,而是独使问题中为有了即将输出,如果问题中从来不于出便非出口。

代码:

 

必威 55必威 56

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 900000
  8 #define MAXP 2222
  9 using namespace std;
 10 int temps[400][1010];
 11 int id[400][1410];
 12 int flows[400][1500];
 13 struct Edge
 14 {
 15     int s,t,f,next;
 16 };
 17 class Dinic
 18 {
 19 public:
 20     Dinic();
 21     void init(int st,int tt);//初始化私有成员
 22     void insert(int st,int tt,int f);//普通最大流插入边
 23     void add_low_up(int st,int tt,int low,int up,int sign);//有上下界最大流插入边,其中sign是用来记录一些点对应的边
 24     void deel();//有上下界最大流后期连超级源汇
 25     bool bfs();//搜索增广路径
 26     void dinic();//非递归求最大流
 27     void reset(int st,int tt);//重置源汇
 28     bool is_True();//判断是否存在满足上下界的最大流
 29     void print_path(int a,int b,int c,int d);//视题目要求进行输出路径或者之类的处理
 30     void getCut();//获取割边S,先使用dinic获取最大流之后使用
 31     void dfs(int start);//在getCut中用来求出S
 32 private:
 33     int s,t;
 34     int ent;
 35     int flow;
 36     int *head;
 37     int *cur;
 38     int *pre;
 39     int *stack;//非递归dinic中模拟栈
 40     Edge *edge;
 41     int *getS;//纪录S;
 42     int *degree;//有源汇有上下界最大流中使用,记录每个点的度数
 43     int sum;//有源汇有上下界最大流中使用,纪录附加边满流时的流量
 44 };
 45 Dinic::Dinic()
 46 {
 47     head=new int[MAXP];
 48     cur=new int[MAXP];
 49     pre=new int[MAXP];
 50     stack=new int[MAXE];
 51     edge=new Edge[MAXE];
 52     getS=new int[MAXP];
 53     degree=new int[MAXP];
 54 }
 55 void Dinic::init(int st,int tt)
 56 {
 57     memset(head,-1,sizeof(int)*MAXP);
 58     memset(degree,0,sizeof(int)*MAXP);
 59     s=st;
 60     t=tt;
 61     ent=0;
 62     flow=0;
 63     sum=0;
 64 }
 65 void Dinic::insert(int st,int tt,int f)
 66 {
 67     edge[ent].s=st;
 68     edge[ent].t=tt;
 69     edge[ent].f=f;
 70     edge[ent].next=head[st];
 71     head[st]=ent++;
 72     edge[ent].s=tt;
 73     edge[ent].t=st;
 74     edge[ent].f=0;
 75     edge[ent].next=head[tt];
 76     head[tt]=ent++;
 77 }
 78 void Dinic::add_low_up(int st,int tt,int low,int up,int sign)
 79 {
 80     degree[st]-=low,degree[tt]+=low;
 81     insert(st,tt,up-low);
 82     if(sign)id[st][tt]=ent-1;
 83 }
 84 void Dinic::deel()
 85 {
 86     for(int i=0; i<s; i++)
 87     {
 88         if(degree[i]<0)
 89             insert(i,t,-degree[i]);
 90         else sum+=degree[i],insert(s,i,degree[i]);
 91     }
 92 }
 93 bool Dinic::bfs()
 94 {
 95     memset(pre,-1,sizeof(int)*MAXP);
 96     pre[s]=0;
 97     queue<int>q;
 98     q.push(s);
 99     while(!q.empty())
100     {
101         int temp1=q.front();
102         q.pop();
103         for(int i=head[temp1]; i!=-1; i=edge[i].next)
104         {
105             int temp2=edge[i].t;
106             if(pre[temp2]==-1&&edge[i].f)
107             {
108                 pre[temp2]=pre[temp1]+1;
109                 q.push(temp2);
110             }
111         }
112     }
113     return pre[t]!=-1;
114 }
115 void Dinic::dinic()
116 {
117     int now;
118     while(bfs())
119     {
120         int top=0;
121         memcpy(cur,head,sizeof(int)*MAXP);
122         int u=s;
123         while(1)
124         {
125             if(u==t)
126             {
127                 int minn=INT_MAX;
128                 for(int i=0; i<top; i++)
129                 {
130                     if(minn>edge[stack[i]].f)
131                     {
132                         minn=edge[stack[i]].f;
133                         now=i;
134                     }
135                 }
136                 for(int i=0; i<top; i++)
137                 {
138                     edge[stack[i]].f-=minn;
139                     edge[stack[i]^1].f+=minn;
140                 }
141                 flow+=minn;
142                 top=now;
143                 u=edge[stack[top]].s;
144             }
145             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)
146                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
147                     break;
148             if(cur[u]==-1)
149             {
150                 if(top==0)break;
151                 pre[u]=-1;
152                 u=edge[stack[--top]].s;
153             }
154             else
155             {
156                 stack[top++]=cur[u];
157                 u=edge[cur[u]].t;
158             }
159         }
160     }
161 }
162 void Dinic::reset(int st,int tt)
163 {
164     s=st,t=tt;
165     flow=0;
166 }
167 bool Dinic::is_True()
168 {
169     deel();
170     dinic();
171     if(sum==flow)
172     {
173         head[s]=-1,head[t]=-1;
174         reset(0,s-1);
175         dinic();
176         return true;
177     }
178     else return false;
179 }
180 void Dinic::print_path(int a,int b,int c,int d)
181 {
182     if(is_True())//有满足上下界的最大流
183     {
184         printf("%d\n",flow);
185         memset(flows,0,sizeof(flows));
186         /*for(int i=a;i<=b;i++)
187             for(int j=c;j<=d;j++)
188                 if(id[i][j])
189                     printf("%d\n",temps[i][j-b]+edge[id[i][j]].f);*/
190         for(int i=a;i<=b;i++)
191         {
192             for(int j=head[i];j!=-1;j=edge[j].next)
193             {
194                 int temp=edge[j].t;
195                 if(temp>=c&&temp<=d)
196                 {
197                     flows[i][temp]+=edge[j^1].f;
198                 }
199             }
200         }
201         for(int i=a;i<=b;i++)
202         {
203             for(int j=c;j<=d;j++)
204             {
205                 if(temps[i][j-b]!=-1)
206                     printf("%d\n",flows[i][j]+temps[i][j-b]);
207             }
208         }
209     }
210     else//没有符合上下界的最大流
211         printf("-1\n");
212     printf("\n");
213 }
214 void Dinic::getCut()
215 {
216     memset(getS,0,sizeof(int)*MAXP);
217     getS[s]=1;
218     dfs(s);
219     for(int i=0; i<MAXP; i++)
220     {
221         if(getS[i])
222             printf("%d ",i);
223     }
224     printf("\n");
225 }
226 void Dinic::dfs(int start)
227 {
228     for(int i=head[start]; i!=-1; i=edge[i].next)
229     {
230         if(edge[i].f)
231         {
232             int temp=edge[i].t;
233             if(!getS[temp])
234             {
235                 getS[temp];
236                 dfs(temp);
237             }
238         }
239     }
240 }
241 int main()
242 {
243     int n,m,num,no,low,up,s,t;
244     Dinic *temp=new Dinic();
245     while(~scanf("%d%d",&n,&m))
246     {
247         memset(id,0,sizeof(id));
248         memset(temps,-1,sizeof(temps));
249         s=0,t=n+m+1;
250         temp->init(t+1,t+2);
251         for(int i=1; i<=m; i++)
252         {
253             scanf("%d",&num);
254             temp->add_low_up(n+i,t,num,INT_MAX,0);
255         }
256         for(int i=1; i<=n; i++)
257         {
258             scanf("%d%d",&num,&up);
259             temp->insert(s,i,up);
260             for(int j=1; j<=num; j++)
261             {
262                 scanf("%d%d%d",&no,&low,&up);
263                 temp->add_low_up(i,no+1+n,low,up,1);
264                 temps[i][no+1]=low;
265             }
266         }
267         temp->insert(t,s,INT_MAX);
268         temp->print_path(1,n,n+1,n+m);
269     }
270     delete temp;
271     return 0;
272 }

View Code

 

poj3692

题意:已掌握班级有g独女孩与b个男孩,所有女生中还互相认识,所有男生之间为竞相认识,给出m对事关表示哪个女孩与谁男孩认识。现在要摘一些学员来组合一个团,使得中装有人数还认,求此团最可怜口。

 思路:这同开之思绪还是要命巧妙的,他的答案就是此图的补图的绝老点权独立集,因为补图中的独立集就是原图中第二划分图备受还发出关联的点集,本人表示从未悟出,看的题解。

 

代码:

必威 57必威 58

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 920000
  8 #define MAXP 100010
  9 using namespace std;
 10 struct Edge
 11 {
 12     int s,t,f,next;
 13 };
 14 class Dinic
 15 {
 16 public:
 17     Dinic();
 18     void insert(int st,int tt,int f);
 19     bool bfs();
 20     void init(int st,int tt);
 21     int dinic();
 22     void getCut();//获取割边S,先使用dinic获取最大流之后使用
 23     void dfs(int start);//在getCut中用来求出S
 24 private:
 25     int s,t;
 26     int ent;
 27     int flow;
 28     int *head;
 29     int *cur;
 30     int *pre;
 31     int *stack;
 32     Edge *edge;
 33     int *getS;
 34 };
 35 Dinic::Dinic()
 36 {
 37     head=new int[MAXP];
 38     cur=new int[MAXP];
 39     pre=new int[MAXP];
 40     stack=new int[MAXE];
 41     edge=new Edge[MAXE];
 42     getS=new int[MAXP];
 43 }
 44 void Dinic::init(int st,int tt)
 45 {
 46     memset(head,-1,sizeof(int)*MAXP);
 47     s=st;
 48     t=tt;
 49     ent=0;
 50     flow=0;
 51 }
 52 void Dinic::insert(int st,int tt,int f)
 53 {
 54     edge[ent].s=st;
 55     edge[ent].t=tt;
 56     edge[ent].f=f;
 57     edge[ent].next=head[st];
 58     head[st]=ent++;
 59     edge[ent].s=tt;
 60     edge[ent].t=st;
 61     edge[ent].f=0;
 62     edge[ent].next=head[tt];
 63     head[tt]=ent++;
 64 }
 65 bool Dinic::bfs()
 66 {
 67     memset(pre,-1,sizeof(int)*MAXP);
 68     pre[s]=0;
 69     queue<int>q;
 70     q.push(s);
 71     while(!q.empty())
 72     {
 73         int temp1=q.front();
 74         q.pop();
 75         for(int i=head[temp1]; i!=-1; i=edge[i].next)
 76         {
 77             int temp2=edge[i].t;
 78             if(pre[temp2]==-1&&edge[i].f)
 79             {
 80                 pre[temp2]=pre[temp1]+1;
 81                 q.push(temp2);
 82             }
 83         }
 84     }
 85     return pre[t]!=-1;
 86 }
 87 int Dinic::dinic()
 88 {
 89     flow=0;
 90     int now;
 91     while(bfs())
 92     {
 93         int top=0;
 94         memcpy(cur,head,sizeof(int)*MAXP);
 95         int u=s;
 96         while(1)
 97         {
 98             if(u==t)
 99             {
100                 int minn=INT_MAX;
101                 for(int i=0; i<top; i++)
102                 {
103                     if(minn>edge[stack[i]].f)
104                     {
105                         minn=edge[stack[i]].f;
106                         now=i;
107                     }
108                 }
109                 for(int i=0; i<top; i++)
110                 {
111                     edge[stack[i]].f-=minn;
112                     edge[stack[i]^1].f+=minn;
113                 }
114                 flow+=minn;
115                 top=now;
116                 u=edge[stack[top]].s;
117             }
118             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)
119                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
120                     break;
121             if(cur[u]==-1)
122             {
123                 if(top==0)break;
124                 pre[u]=-1;
125                 u=edge[stack[--top]].s;
126             }
127             else
128             {
129                 stack[top++]=cur[u];
130                 u=edge[cur[u]].t;
131             }
132         }
133     }
134     return flow;
135 }
136 void Dinic::getCut()
137 {
138     memset(getS,0,sizeof(int)*MAXP);
139     getS[s]=1;
140     dfs(s);
141     for(int i=0;i<MAXP;i++)
142     {
143         if(getS[i])
144             cout<<i<<" ";
145     }
146     cout<<endl;
147 }
148 void Dinic::dfs(int start)
149 {
150     for(int i=head[start];i!=-1;i=edge[i].next)
151     {
152         if(edge[i].f)
153         {
154             int temp=edge[i].t;
155             if(!getS[temp])
156             {
157                 getS[temp];
158                 dfs(temp);
159             }
160         }
161     }
162 }
163 int mp[210][210];
164 int main()
165 {
166     int n,m,k,s,t;
167     int tot=0;
168     Dinic *temp = new Dinic();
169     while(~scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
170     {
171         memset(mp,-1,sizeof(mp));
172         for(int i=1;i<=k;i++)
173         {
174             scanf("%d%d",&s,&t);
175             mp[s][t]=0;
176         }
177         cout<<"Case "<<(++tot)<<": ";
178         temp->init(0,n+m+1);
179         for(int i=1;i<=n;i++)
180         {
181             temp->insert(0,i,1);
182             for(int j=1;j<=m;j++)
183             {
184                 if(mp[i][j])
185                     temp->insert(i,j+n,1);
186             }
187         }
188         for(int i=1;i<=m;i++)
189             temp->insert(i+n,n+m+1,1);
190         printf("%d\n",n+m-temp->dinic());
191     }
192     delete temp;
193     return 0;
194 }

View Code

 

相关文章