long1 vs longpo

Time Limit:1000MS  Memory Limit:65536K
Total Submit:13 Accepted:6

Description

在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

Input

有多组测试数据。
每组测试数据：
第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫约翰已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。
第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

Output

每组测试数据输出一个整数，即排水的最大流量。

Sample Input

5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10 

Sample Output

50

两个代码比较一下，有些东西需要反思
#include<cstdio> #include<cstring> #include<vector> #define M 205 const int inf=99999999; using namespace std; vector<int> node[M]; int n,m,s,t,res,g[M][M]; inline int find(int pre[]) { int q[M]; bool mark[M]; memset(mark,false,sizeof(mark)); int qt,qh,i,x; for(q[0]=s, qt=0, qh=1, mark[s]=true; qt<qh; qt++) { x=q[qt]; i=node[x].size()-1; while(i>=0) { if(g[x][ node[x][i] ]>0 && !mark[ node[x][i] ]) { mark[ node[x][i] ]=true; pre[ node[x][i] ]=x; if(node[x][i]==t) return 1; q[qh++]=node[x][i]; } i--; } } return 0; } inline int ff() { int i,mmin=inf,pre[M],flag,j; if(!find(pre)) return 0; for(i=t; i!=s; i=pre[i]){ if(g[ pre[i] ][i]<mmin) mmin=g[ pre[i] ][i]; } for(i=t; i!=s; i=pre[i]){ flag=1; g[ pre[i] ][i]-=mmin; g[i][ pre[i] ]+=mmin; for(j=node[i].size()-1;j>=0;j--) if(node[i][j]==pre[i]) {flag=0;break;} if(flag) node[i].push_back(pre[i]); } res+=mmin; return 1; } int main() { int i,u,v,z; while(scanf("%d%d",&n,&m) != EOF ) { for(i=0;i<n;i++) node[i].clear(); memset(g,0,sizeof(g)); s=1, t=m; for(i=0;i<n;i++){ scanf("%d%d%d",&u,&v,&z); node[u].push_back(v); g[u][v]+=z; } res=0; while(ff()); printf("%d\n",res); } return 0; } 
 
第二个
#include<cstdio> #include<cstring> #include<vector> #define M 205 #define inf 999999999 using namespace std; //int node[M][M]; int n,m,s,t,res,g[M][M]; inline int find(int pre[]) { int q[M]; bool mark[M]; memset(mark,false,sizeof(mark)); int qt,qh,i,x; for(q[0]=s, qt=0, qh=1, mark[s]=true; qt<qh; qt++) { x=q[qt]; i=1; while(i<=m) { //printf("x=%d i=%d m=%d\n",x,i,m); if(g[x][ i ]>0 && !mark[ i ]) { //printf("%d %d %d\n",x,i,g[x][i]); mark[ i ]=true; pre[ i ]=x; if(i==t) return 1; q[qh++]=i; } i++; } } return 0; } inline int ff() { int i,mmin=inf,pre[M]; //bool flag=false; if(!find(pre)) return 0; for(i=t; i!=s; i=pre[i]){ if(g[ pre[i] ][i]<mmin) mmin=g[ pre[i] ][i]; } for(i=t; i!=s; i=pre[i]){ g[ pre[i] ][i]-=mmin; g[i][ pre[i] ]+=mmin; } res+=mmin; //printf("%d \n",res); return 1; } int main() { //freopen("data.in","r",stdin); int i,u,v,z; while(scanf("%d%d",&n,&m) != EOF ) { //for(i=0;i<=m;i++) node[i].clear(); memset(g,0,sizeof(g)); s=1, t=m; for(i=0;i<n;i++){ scanf("%d%d%d",&u,&v,&z); g[u][v]+=z; } res=0; while(ff()); printf("%d\n",res); } return 0; }