看了一會網絡流的概念，找了個模板就上了。。起初TLE了幾遍，發現是初始化沒搞好。。
sap優化據資料說比EK省好多時間的說，網絡流的精髓應該是構圖，以後碰到難題應該會有所體會的。網絡流有三個性質：一個節點流量守恆（形如電路中的KVL/KCL），流量雙向，f(i,j)<=c(i,j)...
畢竟第一個網絡流模板題的說，直接用SAP了。
[cpp]
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;
const int MAXN=400; //邊數
const int MAXM=40000; //頂點數
const int INF=0x7FFFFFF;
class Edge
{
public:
int a,b; //邊從a->b
int c,f; //容量C,流量f
Edge *next,*back;
void setedge(int a,int b,int c,Edge *next)
{
this->a=a;
this->b=b;
this->c=c;
this->next=next;
this->back=NULL;
this->f=0;
}
};
Edge *edge[MAXN];
Edge nextedge[MAXM];
int dist[MAXN];
int edgenum=0;
int counts[MAXN];
void init(int n)
{
for(int i=0;i<n;i++)
{
edge[i]=NULL;
counts[i]=0;
}
edgenum=0;
}
void init_lable(int n,int s,int t)//頂點個數n,源s,匯t
{
queue<int> que;
que.push(t);
memset(dist,-1,sizeof(dist));
dist[t]=0;
++counts[dist[t]];
while(!que.empty())
{
int now=que.front();
que.pop();
for(Edge *next=edge[now]; next!=NULL;next=next->next)
{
if(next->f!=0)
continue;
int b=next->b;
if(dist[b]==-1)
{
dist[b]=dist[now]+1;
++counts[dist[b]];
que.push(b);
}
}
}
}
void addedge(int x,int y,int c) //添加從x->y的弧，容量為c
{
nextedge[edgenum].setedge(x,y,c,edge[x]);
nextedge[edgenum+1].setedge(y,x,0,edge[y]);
edge[x]=&nextedge[edgenum];
edge[y]=&nextedge[edgenum+1];
edge[x]->back=edge[y];
edge[y]->back=edge[x];
edgenum+=2;
}
int maxflow(int n,int s,int t)
{
int ret=0;
init_lable(n,s,t);
Edge *path[MAXN];
Edge *current[MAXN];
memcpy(current,edge,sizeof(edge));
int path_n=0;//路徑長度
int i=s;
while(1)
{
if(i==t)//找到增廣路
{
int minflow=INF;
int mink;
for(int k=0;k<path_n;k++)
{
if(path[k]->c<minflow)
{
minflow=path[k]->c;
mink=k;
}
}
ret+=minflow;
for(int k=0;k<path_n;k++)
{
path[k]->c-=minflow;
path[k]->back->c+=minflow;
path[k]->f+=minflow;
path[k]->back->f=-(path[k]->f);
}
path_n=mink;
i=path[path_n]->a;
}
if(dist[i]!=0 && counts[dist[i]-1]==0)
break;
Edge *next;
for(next=current[i];next!=NULL;next=next->next)
{
if(next->c==0)
continue;
int y=next->b;
if(dist[i]==dist[y]+1)
break;
}
if(next!=NULL) //允許弧.?
{
current[i]=next;
path[path_n++]=next;
i=next->b;
}
else
{
int minlable=n;
for(Edge *next=edge[i];next!=NULL;next=next->next)
{
if(next->c==0)
continue;
int y=next->b;
if(dist[y]<minlable)
{
minlable=dist[y];
current[i]=next;
}
}
--counts[dist[i]];
dist[i]=minlable+1;
++counts[dist[i]];
if(i!=s)
{
--path_n;
i=path[path_n]->a;
}
else if(dist[i]>n)
{
return ret;
}
}
}
return ret;
}
int main()
{
int maxroute,endr;
while(cin>>maxroute>>endr)
{
init(endr);
int st,ed,p;
for(int i=0;i<maxroute;i++)
{
cin>>st>>ed>>p;
addedge(st,ed,p);
}
int res=maxflow(endr,1,endr);
cout<<res<<endl;
}
return 0;
}
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;
const int MAXN=400; //邊數
const int MAXM=40000; //頂點數
const int INF=0x7FFFFFF;
class Edge
{
public:
int a,b; //邊從a->b
int c,f; //容量C,流量f
Edge *next,*back;
void setedge(int a,int b,int c,Edge *next)
{
this->a=a;
this->b=b;
this->c=c;
this->next=next;
this->back=NULL;
this->f=0;
}
};
Edge *edge[MAXN];
Edge nextedge[MAXM];
int dist[MAXN];
int edgenum=0;
int counts[MAXN];
void init(int n)
{
for(int i=0;i<n;i++)
{
edge[i]=NULL;
counts[i]=0;
}
edgenum=0;
}
void init_lable(int n,int s,int t)//頂點個數n,源s,匯t
{
queue<int> que;
que.push(t);
memset(dist,-1,sizeof(dist));
dist[t]=0;
++counts[dist[t]];
while(!que.empty())
{
int now=que.front();
que.pop();
for(Edge *next=edge[now]; next!=NULL;next=next->next)
{
if(next->f!=0)
continue;
int b=next->b;
if(dist[b]==-1)
{
dist[b]=dist[now]+1;
++counts[dist[b]];
que.push(b);
}
}
}
}
void addedge(int x,int y,int c) //添加從x->y的弧，容量為c
{
nextedge[edgenum].setedge(x,y,c,edge[x]);
nextedge[edgenum+1].setedge(y,x,0,edge[y]);
edge[x]=&nextedge[edgenum];
edge[y]=&nextedge[edgenum+1];
edge[x]->back=edge[y];
edge[y]->back=edge[x];
edgenum+=2;
}
int maxflow(int n,int s,int t)
{
int ret=0;
init_lable(n,s,t);
Edge *path[MAXN];
Edge *current[MAXN];
memcpy(current,edge,sizeof(edge));
int path_n=0;//路徑長度
int i=s;
while(1)
{
if(i==t)//找到增廣路
{
int minflow=INF;
int mink;
for(int k=0;k<path_n;k++)
{
if(path[k]->c<minflow)
{
minflow=path[k]->c;
mink=k;
}
}
ret+=minflow;
for(int k=0;k<path_n;k++)
{
path[k]->c-=minflow;
path[k]->back->c+=minflow;
path[k]->f+=minflow;
path[k]->back->f=-(path[k]->f);
}
path_n=mink;
i=path[path_n]->a;
}
if(dist[i]!=0 && counts[dist[i]-1]==0)
break;
Edge *next;
for(next=current[i];next!=NULL;next=next->next)
{
if(next->c==0)
continue;
int y=next->b;
if(dist[i]==dist[y]+1)
break;
}
if(next!=NULL) //允許弧.?
{
current[i]=next;
path[path_n++]=next;
i=next->b;
}
else
{
int minlable=n;
for(Edge *next=edge[i];next!=NULL;next=next->next)
{
if(next->c==0)
continue;
int y=next->b;
if(dist[y]<minlable)
{
minlable=dist[y];
current[i]=next;
}
}
--counts[dist[i]];
dist[i]=minlable+1;
++counts[dist[i]];
if(i!=s)
{
--path_n;
i=path[path_n]->a;
}
else if(dist[i]>n)
{
return ret;
}
}
}
return ret;
}
int main()
{
int maxroute,endr;
while(cin>>maxroute>>endr)
{
init(endr);
int st,ed,p;
for(int i=0;i<maxroute;i++)
{
cin>>st>>ed>>p;
addedge(st,ed,p);
}
int res=maxflow(endr,1,endr);
cout<<res<<endl;
}
return 0;
}
