就是普通的网络流问题，想试试新学的dinic算法，这个算法暑假就开始看国家集训队论文了，之前一直都只用没效率的EK算法，真正学会这个算法还是开学后白书上的描述：dinic算法就是不断用BFS构建层次图然后用DFS寻找增广。然后就是一下午的WA ，除了第一次调dinic的问题外，这道题竟然有多组数据！！！看discuss里好像还有重边的问题，可我用的邻接表有效避免了这个问题~~
#include <iostream>
#include <cstdio>
#include<string.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=600;
inth=0,dist[maxn]={0},nex[maxn*4+20]={0},root[maxn]={0},point[maxn*4+20]={0},flow[maxn*4+20]={0};
int visit[maxn]={0},m;
int min(int a,int b)
{
int ret=a<b ? a : b;
return ret;
}
void add(int x,int y,int c)
{
nex[++h]=root[x];
point[h]=y;
flow[h]=c;
root[x]=h;
}
void bfs(int src)
{
memset(visit,0,sizeof(visit));
memset(dist,0,sizeof(dist));
int l=0,r=1,que[50000]={0};
que[++l]=src;
visit[src]=1;
while(l<=r)
{
int u=que[l++];
for(int i=root[u];i!=0;i=nex[i])
{
if (flow[i]!=0 && visit[point[i]]==0)
{
que[++r]=point[i];
dist[point[i]]=dist[u]+1;
visit[point[i]]=1;
}
}
}
}
int dfs(int u,int d)
{
if(u==m)return d;
int ret=0;
for(int i=root[u];i!=0 && d;i=nex[i])
{
if (flow[i]!=0 && dist[point[i]]==dist[u]+1)
{
int dd=dfs(point[i],min(d,flow[i]));
flow[i]-=dd;
flow[((i-1) ^ 1)+1]+=dd;//这个构造最赞~~！！
d-=dd;
ret+=dd;
}
}
return ret;
}
int main()
{
int x,y,c,ret;
int n;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(root,0,sizeof(root));
memset(nex,0,sizeof(nex));
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,0);
}
ret=0;
while (1)//dinic
{
bfs(1);
if (visit[m]==0)break;
ret+=dfs(1,inf);
}
printf("%d\n",ret);
}
return 0;
}