学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1532

解题思路：网络流模板

#include <stdio.h><br /> #define Max 205<br /> int N,M;<br /> int Graph[Max][Max];<br /> int pre[Max];/*记录前驱点*/<br /> bool visited[Max];<br /> void InitGraph()<br /> {<br /> int i,j;<br /> for(i=1;i<=M;i++)<br /> {<br /> for(j=1;j<=M;j++)<br /> Graph[i][j] = 0;<br /> }<br /> }<br /> struct Queue<br /> {<br /> int val[Max];<br /> int front,tail;<br /> Queue(){front = tail = 0;}<br /> int Pop()<br /> {<br /> return val[front++];<br /> }<br /> void Push(int x)<br /> {<br /> val[tail++] = x;<br /> }<br /> bool empty()<br /> {<br /> if(front==tail)<br /> return true;<br /> return false;<br /> }<br /> };<br /> bool BFS()<br /> {<br /> int u,v,i;<br /> Queue q;<br /> bool flag = false;<br /> for (i=1;i<=M;i++)<br /> {<br /> pre[i] = -1;<br /> visited[i] = 0;<br /> }<br /> q.Push(1);<br /> visited[1] = 1;<br /> while (!q.empty()&&!flag)<br /> {<br /> u = q.Pop();<br /> for (v=1;v<=M;v++)<br /> {<br /> if (!visited[v]&&Graph[u][v])<br /> {<br /> visited[v] = 1;<br /> pre[v] = u;<br /> q.Push(v);<br /> if(v==M)<br /> {<br /> flag = true;<br /> break;<br /> }<br /> }<br /> }<br /> visited[u] = 1;<br /> }<br /> return flag;<br /> }<br /> int GetMaxFlow()<br /> {<br /> int MaxFlow = 0,min,u,v;<br /> while (BFS())<br /> {<br /> v = M;<br /> min = 0x7fffffff;<br /> while (v!=1)<br /> {<br /> u = pre[v];<br /> if(min>Graph[u][v])<br /> min = Graph[u][v];<br /> v = u;<br /> }<br /> v = M;<br /> while (v!=1)<br /> {<br /> u = pre[v];<br /> Graph[u][v]-=min;<br /> Graph[v][u]+=min;<br /> v = u;<br /> }<br /> MaxFlow+=min;<br /> }<br /> return MaxFlow;<br /> }</p> <p>int main()<br /> {<br /> int a,b,c;<br /> while (scanf("%d%d",&N,&M)!=EOF)<br /> {<br /> InitGraph();<br /> while (N--)<br /> {<br /> scanf("%d%d%d",&a,&b,&c);<br /> Graph[a][b]+=c;/*a->b多条路径，所以相加*/<br /> }<br /> printf("%d/n",GetMaxFlow());<br /> }<br /> return 0;<br /> }