先贴个ISAP的算法模板 从源点s到汇点t 结点共有n个
算法部分基本都是这模板 主要看思路和建图
1 #include<iostream> 2 #include<vector> 3 #include<string.h> 4 #include<queue> 5 #include<cstdio> 6 using namespace std; 7 struct E{int from;int to;int c;int f;}; 8 vector <int> g[220]; 9 vector<E> edge; 10 int d[220],vis[220],cur[220],num[220],p[220]; 11 #define INF 10000000 12 13 void add(int from,int to,int c) 14 { 15 E temp1,temp2; 16 temp1.from =from; temp1.to=to; temp1.c=c;temp1.f=0; 17 temp2.from =to; temp2.to=from; temp2.c=0;temp2.f=0; 18 edge.push_back (temp1); 19 edge.push_back (temp2); 20 int m=edge.size (); 21 g[from].push_back (m-2); 22 g[to].push_back (m-1); 23 } 24 25 void bfs(int s,int t) 26 { 27 int i; 28 queue<int > q; 29 q.push (t); 30 d[t]=0; 31 memset(vis,0,sizeof(vis)); 32 vis[t]=1; 33 while(!q.empty ()) 34 { 35 int t=q.front ();q.pop (); 36 for(i=0;i<g[t].size ();i++) 37 { 38 E e;e=edge[g[t][i]]; 39 if(!vis[e.to]) 40 { 41 q.push (e.to); 42 vis[e.to]=1; 43 d[e.to]=d[t]+1; 44 } 45 } 46 } 47 } 48 49 int zg(int s,int t) 50 { 51 int x=t,a=INF; 52 while(x!=s) 53 { 54 //printf("x %d ",x); 55 E e=edge[p[x]]; 56 if(a>e.c-e.f) 57 a=e.c-e.f; 58 x=e.from; 59 } 60 x=t; 61 while(x!=s) 62 { 63 edge[p[x]].f+=a; 64 edge[p[x]^1].f-=a; 65 x=edge[p[x]].from ; 66 } 67 return a; 68 } 69 70 int maxflow(int s,int t,int n) 71 { 72 int flow=0,i; 73 bfs(s,t); 74 memset(num,0,sizeof(num)); 75 memset(cur,0,sizeof(cur)); 76 for(i=0;i<=t;i++) 77 num[d[i]]++; 78 int x=s; 79 while(d[s]<=n) 80 { 81 if(x==t) 82 { 83 flow+=zg(s,t); 84 x=s; 85 //printf("flow %d ",flow); 86 } 87 int ok=0; 88 for(i=cur[x];i<g[x].size ();i++) 89 { 90 E e; 91 e=edge[g[x][i]]; 92 if(e.c>e.f&&d[x]==d[e.to]+1) 93 { 94 ok=1; 95 96 p[e.to]=g[x][i]; 97 98 cur[x]=i; 99 x=e.to;//!@#$%^& 100 break; 101 } 102 } 103 if(ok==0) 104 { 105 int m=n; 106 for(i=0;i<g[x].size ();i++) 107 { 108 E e; 109 e=edge[g[x][i]]; 110 if(e.c>e.f&&m>d[e.to]) 111 m=d[e.to]; 112 } 113 if(--num[d[x]]==0) break; 114 num[d[x]=m+1]++; 115 cur[x]=0;////!@#$%^^& 116 if(x!=s) 117 x=edge[p[x]].from ; 118 119 } 120 } 121 return flow; 122 }
poj 1149 pigs
http://poj.org/problem?id=1149
题意： 有m个猪栏和 n个来买猪的人 给出每个猪栏里的数量 和 每个来的人能开的猪栏标号 和他要买的猪的数量 他打开这些门后可以将 里面的猪重新分配 求 最多可以卖多少猪
思路：网络流 将来的人 和 开某一个猪栏的门则 这个人和源点连一条边 容量为 这个猪栏里 的猪的数量 而若是那个猪栏已经被人打开过也就是 可能之前就被重新分配了 则这个人 和前面 的这个人连一条 无限大的边 最后这n个人各和 汇点连一条边 容量为 他要买的猪的数量
1 #include<iostream> 2 #include<vector> 3 #include<string.h> 4 #include<queue> 5 using namespace std; 6 struct E{int from;int to;int c;int f;}; 7 vector <int> g[202]; 8 vector<E> edge; 9 int d[102],vis[102],cur[102],num[102],p[102],w[1102],need[120],n; 10 #define INF 10000000 11 12 void add(int from,int to,int c) 13 { 14 E temp1,temp2; 15 temp1.from =from; temp1.to=to; temp1.c=c;temp1.f=0; 16 temp2.from =to; temp2.to=from; temp2.c=0;temp2.f=0; 17 edge.push_back (temp1); 18 edge.push_back (temp2); 19 int m=edge.size (); 20 g[from].push_back (m-2); 21 g[to].push_back (m-1); 22 } 23 24 void bfs(int s,int t) 25 { 26 int i; 27 queue<int > q; 28 q.push (t); 29 d[t]=0; 30 memset(vis,0,sizeof(vis)); 31 vis[t]=1; 32 while(!q.empty ()) 33 { 34 int t=q.front ();q.pop (); 35 for(i=0;i<g[t].size ();i++) 36 { 37 E e;e=edge[g[t][i]]; 38 if(!vis[e.to]) 39 { 40 q.push (e.to); 41 vis[e.to]=1; 42 d[e.to]=d[t]+1; 43 } 44 } 45 } 46 } 47 48 int zg(int s,int t) 49 { 50 int x=t,a=INF; 51 while(x!=s) 52 { 53 //printf("x %d ",x); 54 E e=edge[p[x]]; 55 if(a>e.c-e.f) 56 a=e.c-e.f; 57 x=e.from; 58 } 59 x=t; 60 while(x!=s) 61 { 62 edge[p[x]].f+=a; 63 edge[p[x]^1].f-=a; 64 x=edge[p[x]].from ; 65 } 66 return a; 67 } 68 69 int maxflow(int s,int t,int n) 70 { 71 int flow=0,i; 72 bfs(s,t); 73 memset(num,0,sizeof(num)); 74 memset(cur,0,sizeof(cur)); 75 for(i=0;i<=t;i++) 76 num[d[i]]++; 77 int x=s; 78 while(d[s]<n) 79 { 80 if(x==t) 81 { 82 flow+=zg(s,t); 83 x=s; 84 //printf("flow %d ",flow); 85 } 86 int ok=0; 87 for(i=cur[x];i<g[x].size ();i++) 88 { 89 E e; 90 e=edge[g[x][i]]; 91 if(e.c>e.f&&d[x]==d[e.to]+1) 92 { 93 ok=1; 94 95 p[e.to]=g[x][i]; 96 97 cur[x]=i; 98 x=e.to;//!@#$%^& 99 break; 100 } 101 } 102 if(ok==0) 103 { 104 int m=n; 105 for(i=0;i<g[x].size ();i++) 106 { 107 E e; 108 e=edge[g[x][i]]; 109 if(e.c>e.f&&m>d[e.to]) 110 m=d[e.to]; 111 } 112 if(--num[d[x]]==0) break; 113 num[d[x]=m+1]++; 114 cur[x]=0;////!@#$%^^& 115 if(x!=s) 116 x=edge[p[x]].from ; 117 118 } 119 } 120 return flow; 121 } 122 123 124 int main() 125 { 126 int i,j,m,t,pp[1102],u,num; 127 while(~scanf("%d%d",&m,&n)) 128 { 129 memset(pp,-1,sizeof(pp)); 130 for(i=1;i<=m;i++) 131 { 132 scanf("%d",&w[i]); 133 // add(0,i,w[i]); 134 } 135 136 137 for(i=1;i<=n;i++) 138 { 139 scanf("%d",&num); 140 while(num--) 141 { 142 scanf("%d",&u); 143 if(pp[u]==-1) 144 { 145 add(0,i,w[u]); 146 pp[u]=i; 147 } 148 else 149 { 150 add(pp[u],i,INF); 151 pp[u]=i; 152 } 153 154 } 155 scanf("%d",&need[i]); 156 } 157 for(i=1;i<=n;i++) 158 add(i,n+1,need[i]); 159 int ans=maxflow(0,n+1,n+1); 160 printf("%d ",ans); 161 edge.clear (); 162 for(i=0;i<=n+1;i++) 163 g[i].clear (); 164 } 165 return 0; 166 }
poj 2455 Secret Milking Machine
http://poj.org/problem?id=2455
题意：FJ有N块地，这些地之间有P条双向路，每条路的都有固定的长度l。现在要你找出从第1块地到第n块地的T条不同路径，每条路径上的路不能与先前的路径重复，问这些路径中的最长路的最小是多少。（注意找的是 路径 是两两之间的 路径）
思路：路径不能重复 想到网络流 找最大的最小 想到二分，
二分这个值为mid 要是 i 到 j 有路 且 他们的长度<=mid 就把 i到j连一条边容量为1 s为1 t为 n 求最大流 最大流就是他们不同的路径 的数量
注意： 因为是无向图 所以建边要建两条
add(ee[i].x,ee[i].y,1);
add(ee[i].y,ee[i].x,1);
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<vector> 5 #include<queue> 6 using namespace std; 7 8 #define INF 10000000 9 struct node{int x;int y;int w;}ee[40002]; 10 struct E{int from;int to;int f;int c;}; 11 vector<E> edge; 12 vector<int > g[202]; 13 int num[202],d[202],vis[202],cur[202],p[202]; 14 15 void add(int from,int to,int c) 16 { 17 E temp1,temp2; 18 temp1.from =from; temp1.to=to; temp1.c=c;temp1.f=0; 19 temp2.from =to; temp2.to=from; temp2.c=0;temp2.f=0; 20 edge.push_back (temp1); 21 edge.push_back (temp2); 22 int m=edge.size (); 23 g[from].push_back (m-2); 24 g[to].push_back (m-1); 25 } 26 27 void bfs(int s,int t) 28 { 29 int i; 30 queue<int > q; 31 q.push (t); 32 d[t]=0; 33 memset(vis,0,sizeof(vis)); 34 vis[t]=1; 35 while(!q.empty ()) 36 { 37 int t=q.front ();q.pop (); 38 for(i=0;i<g[t].size ();i++) 39 { 40 E e;e=edge[g[t][i]]; 41 if(!vis[e.to]) 42 { 43 q.push (e.to); 44 45 46 int zg(int s,int t) 47 { 48 int x=t,a=INF; 49 while(x!=s) 50 { 51 E e=edge[p[x]]; 52 if(a>e.c-e.f) 53 a=e.c-e.f; 54 x=e.from; 55 } 56 x=t; 57 while(x!=s) 58 { 59 edge[p[x]].f+=a; 60 edge[p[x]^1].f-=a; 61 x=edge[p[x]].from ; 62 } 63 return a; 64 } 65 66 int maxflow(int s,int t,int n) 67 { 68 int flow=0,i; 69 bfs(s,t); 70 memset(num,0,sizeof(num)); 71 memset(cur,0,sizeof(cur)); 72 for(i=0;i<=t;i++) 73 num[d[i]]++; 74 int x=s; 75 while(d[s]<n) 76 { 77 if(x==t) 78 { 79 flow+=zg(s,t); 80 x=s; 81 } 82 int ok=0; 83 for(i=cur[x];i<g[x].size ();i++) 84 { 85 E e; 86 e=edge[g[x][i]]; 87 if(e.c>e.f&&d[x]==d[e.to]+1) 88 { 89 ok=1; 90 91 p[e.to]=g[x][i]; 92 93 cur[x]=i; 94 x=e.to; 95 break; 96 } 97 } 98 if(ok==0) 99 { 100 int m=n; 101 for(i=0;i<g[x].size ();i++) 102 { 103 E e; 104 e=edge[g[x][i]]; 105 if(e.c>e.f&&m>d[e.to]) 106 m=d[e.to]; 107 } 108 if(--num[d[x]]==0) break; 109 num[d[x]=m+1]++; 110 cur[x]=0; 111 if(x!=s) 112 x=edge[p[x]].from ; 113 114 } 115 } 116 return flow; 117 } 118 119 int main() 120 { 121 int i,j,m,n,t,p; 122 while(~scanf("%d%d%d",&n,&m,&p)) 123 { 124 125 126 int minn=INF,maxx=0; 127 for(i=0;i<m;i++) 128 { 129 scanf("%d%d%d",&ee[i].x,&ee[i].y,&ee[i].w); 130 if(ee[i].w>maxx) 131 maxx=ee[i].w; 132 if(ee[i].w<minn) 133 minn=ee[i].w; 134 } 135 136 137 int low=minn,high=maxx; 138 int best; 139 while(low<=high) 140 { 141 int mid=(high+low)/2; 142 143 edge.clear(); 144 for(i=0;i<=n;i++) 145 g[i].clear(); 146 147 for(i=0;i<m;i++) 148 if(ee[i].w<=mid) 149 { 150 add(ee[i].x,ee[i].y,1); 151 add(ee[i].y,ee[i].x,1); 152 153 } 154 155 int ans=maxflow(1,n,n); 156 157 if(ans>=p) 158 { 159 best=mid; 160 high=mid-1; 161 } 162 else low=mid+1; 163 } 164 printf("%d ",best); 165 166 167 } 168 return 0; 169 }