34 / 81 Problem A POJ 3436 ACM Computer Factory
没懂。。
此题是最大流问题。题目意思比较难懂。
看得比较纠结。
就是说有N台组装电脑的机器。电脑的组成部分共有P部分。
每台机器有P个输入输出规格。还有一个容量Q；
其中输入规格有三种情况：0,1,2
0：该部分不能存在
1：该部分必须保留
2：该部分可有可无
输出规格有2种情况：0,1
0：该部分不存在
1：该部分存在
要求的是生产电脑最大的台数，就是求网络中的最大流。
这相当于是生产线。需要自己去建图。
但是考虑到每台机器都有容量，所以把一台机器分成两个点，中间建一条容量的边。
同时如果一台机器的输出符合另一台机器的输入，则建一条容量无穷大的边。
同时要增加源点和汇点。输入没有1的连接源点，输出全部是1的连接汇点。
92 / 195 Problem B POJ 3281 Dining
本题能够想到用最大流做，那真的是太绝了。建模的方法很妙！
题意就是有N头牛，F个食物，D个饮料。
N头牛每头牛有一定的喜好，只喜欢几个食物和饮料。
每个食物和饮料只能给一头牛。一头牛只能得到一个食物和饮料。
而且一头牛必须同时获得一个食物和一个饮料才能满足。问至多有多少头牛可以获得满足。
最初相当的是二分匹配。但是明显不行，因为要分配两个东西，两个东西还要同时满足。
最大流建图是把食物和饮料放在两端。一头牛拆分成两个点，两点之间的容量为1.喜欢的食物和饮料跟牛建条边，容量为1.
加个源点和汇点。源点与食物、饮料和汇点的边容量都是1，表示每种食物和饮料只有一个。
这样话完全是最大流问题了，。
/* POJ 3281 最大流 //源点-->food-->牛(左)-->牛(右)-->drink-->汇点 //精髓就在这里，牛拆点，确保一头牛就选一套food和drink的搭配 */ #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<queue> using namespace std; //**************************************************** //最大流模板 //初始化：g[][],start,end //****************************************************** const int MAXN=500; const int INF=0x3fffffff; int g[MAXN][MAXN];//存边的容量，没有边的初始化为0 int path[MAXN],flow[MAXN],start,end; int n;//点的个数，编号0-n.n包括了源点和汇点。 queue<int>q; int bfs() { int i,t; while(!q.empty())q.pop();//把清空队列 memset(path,-1,sizeof(path));//每次搜索前都把路径初始化成-1 path[start]=0; flow[start]=INF;//源点可以有无穷的流流进 q.push(start); while(!q.empty()) { t=q.front(); q.pop(); if(t==end)break; //枚举所有的点，如果点的编号起始点有变化可以改这里 for(i=0;i<=n;i++) { if(i!=start&&path[i]==-1&&g[t][i]) { flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i]; q.push(i); path[i]=t; } } } if(path[end]==-1)return -1;//即找不到汇点上去了。找不到增广路径了 return flow[end]; } int Edmonds_Karp() { int max_flow=0; int step,now,pre; while((step=bfs())!=-1) { max_flow+=step; now=end; while(now!=start) { pre=path[now]; g[pre][now]-=step; g[now][pre]+=step; now=pre; } } return max_flow; } int main() { int N,F,D; while(scanf("%d%d%d",&N,&F,&D)!=EOF) { memset(g,0,sizeof(g)); n=F+D+2*N+1; start=0; end=n; for(int i=1;i<=F;i++)g[0][i]=1; for(int i=F+2*N+1;i<=F+2*N+D;i++)g[i][n]=1; for(int i=1;i<=N;i++)g[F+2*i-1][F+2*i]=1; int k1,k2; int u; for(int i=1;i<=N;i++) { scanf("%d%d",&k1,&k2); while(k1--) { scanf("%d",&u); g[u][F+2*i-1]=1; } while(k2--) { scanf("%d",&u); g[F+2*i][F+2*N+u]=1; } } printf("%d ",Edmonds_Karp()); } return 0; }
55 / 148 Problem C POJ 1087 A Plug for UNIX
题意：在一个房间里有N种插座和使用M种插座的电器，，这M种插座有些在现有的插座中不包含，不过可以通过适配器来转化，有K种类型的适配器来转化，让你求最少会有多少电器没法使用插座。
思路:最大二分匹配。即求出最多有多少电器有相应的插座，然后用M减去就是所求，不过建图有点难想，我也是看了别人的解题报告才明白的。将电器和相应的插座类型连接起来，将能相互转化的插座连接起来，然后将不能直接使用N种插座而通过适配器的转换就能用的电器和插座连起来，然后就是求M种电器和Ｎ种插座的最大匹配了。呃，其实看到很多博客都是用最大流做的，原本这题也是在最大流的练习中找到的，但是我发现最大匹配更好理解，而且二分匹配加上源点和汇点就能转化成最大流。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <map> #include <string> #define N 505 using namespace std ; map<string , int>p ; int mp[N][N] ; int n , m , k , nx ; int f[N] , d[N] ; int dfs( int x ) { int i ; for ( i = m + 1; i <= m + nx ; i++ ) { if ( !f[i] && mp[x][i] ) { f[i] = 1 ; if ( !d[i] || dfs( d[i] )) { d[i] = x ; return 1 ; } } } return 0 ; } //二分匹配模板 int floyd( ) { int i , sum ; sum = 0 ; memset( d , 0 , sizeof ( d )); for ( i = 1 ; i <= m ; i++ ) { memset( f , 0 , sizeof ( f )); if ( dfs( i )) sum++; } return sum ; } int main() { int i , j , t ; string str1 , str2 ; //freopen("input.txt" , "r" , stdin ); //输入N种插座 scanf ( "%d" , &n ) ; p.clear(); nx = n ; for ( i = 1 ; i <= n ; i++ ) { cin>>str1 ; p[str1] = i ; } //输入M种电器 scanf ( "%d" , &m ); for ( i = 1 ; i <= m ; i++ ) { cin>>str1>>str2 ; if ( p[str2] != 0 ) { int x = p[str2] ; mp[i][x+m] = 1 ; } else { n++ ; p[str2] = n ; mp[i][n+m] = 1 ; } } //输入K种转化关系 scanf ( "%d" , &k ); for ( i = 1 ; i <= k ; i++ ) { cin>>str1>>str2 ; if ( p[str1] == 0 ) { n++ ; p[str1] = n ; } if ( p[str2] == 0 ) { n++ ; p[str2] = n ; } mp[p[str1]+m][p[str2]+m] = 1 ; } //将通过适配器可以使用原来N种插座的电器连起来。 for ( i = 1 ; i <= m + n ; i++ ) for ( j = 1 ; j <= m + n ; j++ ) for ( t = 1 ; t <= m + n ; t++ ) if ( mp[j][i] && mp[i][t] && !mp[j][t] ) mp[j][t] = 1 ; int flow = floyd( ); printf ( "%d " , m - flow ) ; return 0; }
最大流代码
#include<stdio.h> #include<map> #include<iostream> #include<string.h> #include<string> #include<queue> using namespace std; //**************************************************** //最大流模板 //初始化：g[][],start,end //****************************************************** const int MAXN=500; const int INF=0x3fffffff; int g[MAXN][MAXN];//存边的容量，没有边的初始化为0 int path[MAXN],flow[MAXN],start,end; int n;//点的个数，编号0-n.n包括了源点和汇点。 queue<int>q; int bfs() { int i,t; while(!q.empty())q.pop();//把清空队列 memset(path,-1,sizeof(path));//每次搜索前都把路径初始化成-1 path[start]=0; flow[start]=INF;//源点可以有无穷的流流进 q.push(start); while(!q.empty()) { t=q.front(); q.pop(); if(t==end)break; //枚举所有的点，如果点的编号起始点有变化可以改这里 for(i=0;i<=n;i++) { if(i!=start&&path[i]==-1&&g[t][i]) { flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i]; q.push(i); path[i]=t; } } } if(path[end]==-1)return -1;//即找不到汇点上去了。找不到增广路径了 return flow[end]; } int Edmonds_Karp() { int max_flow=0; int step,now,pre; while((step=bfs())!=-1) { max_flow+=step; now=end; while(now!=start) { pre=path[now]; g[pre][now]-=step; g[now][pre]+=step; now=pre; } } return max_flow; } map<string,int>hash; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); string str1,str2; int N,M; int tol; while(scanf("%d",&N)!=EOF) { hash.clear(); memset(g,0,sizeof(g)); start=0; end=1; tol=2; while(N--) { cin>>str1; hash[str1]=tol; g[0][tol]=1; tol++; } scanf("%d",&M); for(int i=0;i<M;i++) { cin>>str1>>str2; if(hash[str1]==0)hash[str1]=tol++; if(hash[str2]==0)hash[str2]=tol++; g[hash[str1]][end]=1; g[hash[str2]][hash[str1]]=1; } scanf("%d",&N); while(N--) { cin>>str1>>str2; if(hash[str1]==0)hash[str1]=tol++; if(hash[str2]==0)hash[str2]=tol++; g[hash[str2]][hash[str1]]=INF; } n=tol-1; printf("%d ",M-Edmonds_Karp()); } return 0; }
59 / 111 Problem D POJ 2195 Going Home
hint.做过的题，解题报告见以前博客
44 / 132 Problem E POJ 2516 Minimum Cost
hint.做过的题，解题报告见以前博客
35 / 72 Problem F POJ 1459 Power Network
hint.做过的题，解题报告见以前博客
40 / 217 Problem G HDU 4280 Island Transport
题意：有N个岛屿之间有M双向条路，每条路每个小时最多能通过C个人，现在问一个小时内，最多能把多少个顾客从最西边的岛屿送至最东边的岛屿上。
思路：网络流，求最大流。建图：每条路连接的两个岛屿之间建立一条容量为C的双向边，取超级源点与汇点，源点与最西边的岛屿，汇点与最东边的岛屿建立一条流量为无穷大的边。
/* 最大流模板 sap */ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; const int MAXN=100010;//点数的最大值 const int MAXM=400010;//边数的最大值 const int INF=0x3f3f3f3f; struct Node { int from,to,next; int cap; }edge[MAXM]; int tol; int head[MAXN]; int dep[MAXN]; int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y int n;//n是总的点的个数，包括源点和汇点 void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++; } void BFS(int start,int end) { memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=1; int que[MAXN]; int front,rear; front=rear=0; dep[end]=0; que[rear++]=end; while(front!=rear) { int u=que[front++]; if(front==MAXN)front=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dep[v]!=-1)continue; que[rear++]=v; if(rear==MAXN)rear=0; dep[v]=dep[u]+1; ++gap[dep[v]]; } } } int SAP(int start,int end) { int res=0; BFS(start,end); int cur[MAXN]; int S[MAXN]; int top=0; memcpy(cur,head,sizeof(head)); int u=start; int i; while(dep[start]<n) { if(u==end) { int temp=INF; int inser; for(i=0;i<top;i++) if(temp>edge[S[i]].cap) { temp=edge[S[i]].cap; inser=i; } for(i=0;i<top;i++) { edge[S[i]].cap-=temp; edge[S[i]^1].cap+=temp; } res+=temp; top=inser; u=edge[S[top]].from; } if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路 break; for(i=cur[u];i!=-1;i=edge[i].next) if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1) break; if(i!=-1) { cur[u]=i; S[top++]=i; u=edge[i].to; } else { int min=n; for(i=head[u];i!=-1;i=edge[i].next) { if(edge[i].cap==0)continue; if(min>dep[edge[i].to]) { min=dep[edge[i].to]; cur[u]=i; } } --gap[dep[u]]; dep[u]=min+1; ++gap[dep[u]]; if(u!=start)u=edge[S[--top]].from; } } return res; } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int start,end; int m; int u,v,z; int T; scanf("%d",&T); while(T--) { init(); scanf("%d%d",&n,&m); int minx=10000000; int maxx=-10000000; int x,y; for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); if(minx>x) { minx=x; start=i; } if(maxx<x) { maxx=x; end=i; } } while(m--) { scanf("%d%d%d",&u,&v,&z); addedge(u,v,z); addedge(v,u,z); } //n一定是点的总数，这是使用SAP模板需要注意的 int ans=SAP(start,end); printf("%d ",ans); } return 0; }
42 / 133 Problem H HDU 4292 Food
题意：有F种食物 D种饮料 它们都有一定的数量 有N个人 每个人都有自己喜欢吃的食物和饮料 （每个人至少要一种食物和饮料） 只有能满足他的要求时他才会接服务 求最大能满足多少人？
思路：网络流 建一超级源点 汇点 源点与食物相连 边权为其数量，汇点与饮料相连 边权也为其数量 把人分成两个点 之间的边权为1 每个人与之需要的食物和饮料相连 边权为1
/* 题意：F种食物和D种饮料，每种食物和饮料的数目也是固定的，总共有N位顾客，每位顾客都只吃喝固定种类的食品 饮料，问最多能满足多少为顾客。 题解：最大流+拆点； 建图：将每位顾客拆成两个点，同一顾客之间加入权值为1的有向边限制了只能是一位一位顾客来满足，再加入源点 来连接每一种食物，权值为该食物数量，然后根据顾客喜欢的食物连接顾客，权值为1，因为每位顾客只需1份食物饮 料，然后加入饮料结点并根据顾客喜好连接，权值同样为1，然后将饮料与汇点连接，权值为饮料的数目，最终求得 的最大流即为最多能满足的顾客。 */ #include <cstdio> #include <cstring> #define EMAX 200000 #define VMAX 1005 const int INF = 0xfffffff; int head[VMAX],dis[VMAX],cur[VMAX],gap[VMAX],pre[VMAX]; int EN; struct edge { int from,to; int weight; int next; }e[EMAX]; void insert(int u,int v,int w) { e[EN].to = v; e[EN].weight = w; e[EN].next = head[u]; head[u] = EN++; e[EN].weight = 0; e[EN].to = u; e[EN].next = head[v]; head[v] = EN++; } int sap(int s,int t, int n) { memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); for(int i=0; i<=n; i++) cur[i] = head[i]; int u = pre[s]; pre[s] = s; int ret = 0; int temp = -1; gap[0] = n; bool flag; while(dis[s] < n) { flag = false; for(int &i = cur[u]; i != -1; i = e[i].next) { int v = e[i].to; if(e[i].weight && dis[u] == dis[v] + 1) { if (temp == -1 || temp>e[i].weight) temp = e[i].weight; pre[v] = u; u = v; if(v == t) { ret += temp; for(u = pre[u];v != s;v = u,u = pre[u]) { e[cur[u]].weight -= temp; e[cur[u]^1].weight += temp; } temp = -1; } flag = true; break; } } if (flag) continue; int mindis = n; for(int i = head[u]; i != -1 ; i = e[i].next) { int v = e[i].to; if(e[i].weight && mindis > dis[v]) { cur[u] = i; mindis = dis[v]; } } gap[dis[u]]--; if( gap[dis[u]] == 0) break; dis[u] = mindis+1; gap[dis[u]]++; u = pre[u]; } return ret; } int main(void) { int n,f,d,t; char s[205]; while (scanf("%d%d%d",&n,&f,&d) == 3) { memset(head,-1,sizeof(head)); EN = 0; for(int i=1; i<=f; i++) { scanf("%d",&t); insert(0,i,t);//源点加边 } for(int i=1; i<=d; i++) { scanf("%d",&t); insert(f+2*n+i,f+2*n+d+1,t);//汇点加边 } for(int i=1; i<=n; i++) insert(f+i,f+n+i,1);//拆点 for(int i=1; i<=n; i++) { scanf("%s",s+1); for(int j=1; j<=f; j++) if (s[j] == 'Y') insert(j,f+i,1);//顾客与食物加边 } for(int i=1; i<=n; i++) { scanf("%s",s+1); for(int j=1; j<=d; j++) if (s[j] == 'Y') insert(f+n+i,f+2*n+j,1);//顾客与饮料加边 } printf("%d ",sap(0,f+2*n+d+1,f+2*n+d+2)); } return 0; }
34 / 90 Problem I HDU 4289 Control
成都赛区网络赛1002题。
一场网络赛两题最大流，用SAP模板可以秒掉。
//1002 /* HDU 4289 G++ 62ms 1888K 最大流 SAP */ #include<stdio.h> #include<iostream> #include<map> #include<set> #include<algorithm> #include<string.h> #include<stdlib.h> using namespace std; const int MAXN=5000;//点数的最大值 const int MAXM=2500000;//边数的最大值 const int INF=0x3f3f3f3f; struct Node { int from,to,next; int cap; }edge[MAXM]; int tol; int head[MAXN]; int dep[MAXN]; int gap[MAXN];//gap[x]=y:说明残留网络中 dep[i]==x的个数为y int n;//点的实际个数，一定是总的点的个数，包括源点和汇点 void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++; } void BFS(int start,int end) { memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=1; int que[MAXN]; int front,rear; front=rear=0; dep[end]=0; que[rear++]=end; while(front!=rear) { int u=que[front++]; if(front==MAXN)front=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap!=0||dep[v]!=-1)continue; que[rear++]=v; if(rear==MAXN)rear=0; dep[v]=dep[u]+1; ++gap[dep[v]]; } } } int SAP(int start,int end) { int res=0; BFS(start,end); int cur[MAXN]; int S[MAXN]; int top=0; memcpy(cur,head,sizeof(head)); int u=start; int i; while(dep[start]<n) { if(u==end) { int temp=INF; int inser; for(i=0;i<top;i++) if(temp>edge[S[i]].cap) { temp=edge[S[i]].cap; inser=i; } for(i=0;i<top;i++) { edge[S[i]].cap-=temp; edge[S[i]^1].cap+=temp; } res+=temp; top=inser; u=edge[S[top]].from; } if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路 break; for(i=cur[u];i!=-1;i=edge[i].next) if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1) break; if(i!=-1) { cur[u]=i; S[top++]=i; u=edge[i].to; } else { int min=n; for(i=head[u];i!=-1;i=edge[i].next) { if(edge[i].cap==0)continue; if(min>dep[edge[i].to]) { min=dep[edge[i].to]; cur[u]=i; } } --gap[dep[u]]; dep[u]=min+1; ++gap[dep[u]]; if(u!=start) u=edge[S[--top]].from; } } return res; } int main() { //freopen("B.in","r",stdin); //freopen("B.out","w",stdout); int N,M; int u,v; int start; int end; while(scanf("%d%d",&N,&M)!=EOF) { init(); scanf("%d%d",&start,&end); start=2*start-1; end=2*end; n=2*N; for(int i=1;i<=N;i++) { scanf("%d",&u); addedge(2*i-1,2*i,u); addedge(2*i,2*i-1,u); } while(M--) { scanf("%d%d",&u,&v); addedge(2*u,2*v-1,INF); addedge(2*v,2*u-1,INF);//这里一定要注意 } printf("%d ",SAP(start,end)); } return 0; }
28 / 90 Problem J UVA 10480 Sabotage
最大流
19 / 37 Problem K HDU 2732 Leapin' Lizards
最大流
13 / 136 Problem L HDU 3338 Kakuro Extension
很神奇的最大流的题目。很有意思。
题目意思就是在n*m的格子中，有黑白两种格子。要在白格子中填入数字1~9
* 每一段横竖连续的白格子的和是知道的。
* 求出一种满足的，保证有解。
* 最大流。
* 按照横竖段进行编号。然后行进列出，构造图形。
*
* 为了保证填入的数字是1~9，所以一开始每个格子减掉了1，相应的流入和流出都减掉。
* 然后格子的边的赋值为8.
* 还有就是要记录下相应边的编号，便于输出结果。
36 / 358 Problem M HDU 3605 Escape
这题一看题目是很简单的最大流。
但是数据好大，试了很多模板，都是TLE。
后来发现可以合并点，
因为m<=10.
所以用二进制记录。
在n个点中，如果是一样的就合并。
这样最多是1024+m+2个点。
但是这题还是很坑。。。。在HDU上用G++交无论如何都是TLE的。直接读入数据输出都是TLE.
改成C++就AC了。。。
17 / 58 Problem N HDU 3081 Marriage Match II
最大流+二分+并查集
15 / 61 Problem O HDU 3416 Marriage Match IV
这题就是求从A到B的最短路径的条数。
一条边只能经过一次。
先通过最短路去除掉没有用的边。
然后用一次最大流就是答案了。
从A和B分别出发求最短路dist1,dist2.
注意从B求得额时候要反向。
如果dist1[a]+dist2[b]+c==dist1[B].那么这条边就是有用的。。
我用的SPFA求最短路的。