网络流。
题意非常easy。给出单向边，容量。
找最大流。注意重边要加起来。g[u][v].c+=c;
第一次写网络流。
也是第一个网络流的题。
看了两天，理解了之后就唰唰唰的写出来了。
大概可能是EK吧。
ORZ都不知道用的啥算法。仅仅是感觉要这样写。由于重边还WA了。改了就AC。
PS：事实上网络流的教程这么多。
个人感觉就是DFS或者BFS找增广路，然后改动流量。看懂了就不算难。
难的是怎样建立流量图模型。
不会每道题都想这个这么裸。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
#define acfun std::ios::sync_with_stdio(false)
using namespace std;
struct type
{int c,f;
};
type g[1001][1001];
bool vis[1001];
int prev[1001];
int alpha[1001];
int n,m;void EK(int start,int thend)
{int maxflow=0;while(1){for(int i=0; i<=n; i++)vis[i]=prev[i]=alpha[i]=0;queue<int>q;q.push(start);vis[start]=1;alpha[start]=INF;while(!q.empty()&&!vis[thend]){int u=q.front();q.pop();for(int j=1; j<=n; j++){if(vis[j])continue;if(g[u][j].f<g[u][j].c){vis[j]=1;prev[j]=u;alpha[j]=min(alpha[u],g[u][j].c-g[u][j].f);q.push(j);}else if(g[j][u].f>0){vis[j]=1;prev[j]=u;alpha[j]=min(alpha[u],g[j][u].f);q.push(j);}}}if(vis[thend]==0||alpha[thend]==0)break;int k1=thend,k2=prev[thend];int tmp=alpha[thend];maxflow+=tmp;while(1){if(g[k2][k1].f<g[k2][k1].c)g[k2][k1].f+=tmp;elseg[k1][k2].f-=tmp;k1=k2;k2=prev[k1];if(k2==0)break;}}printf("%d\n",maxflow);
}
int main()
{while(scanf("%d%d",&m,&n)!=EOF){for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)g[i][j].c=g[i][j].f=0;int u,v,c;while(m--){scanf("%d%d%d",&u,&v,&c);g[u][v].c+=c;}EK(1,n);}
}
