極·郭际泽 @ 2018-12-22 09:53:20
评测记录
code:(推送-重贴标签算法)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF=1073741823;
struct edge
{
int to;
int cap;
};
struct listbase
{
edge val;
int next;
}net[110001];
int n,m;
int s,t;
queue<int> overflow;
int flow[110001];
int over[10001];
int h[10001];
void push(int p)
{
int now=p;
while(now!=-1)
{
edge v=net[now].val;
int val=min(over[p],v.cap-flow[now]);
if(val!=0 && h[p]>h[v.to])
{
if(over[v.to]==0 && v.to!=s && v.to!=t)
overflow.push(v.to);
over[p]-=val;
over[v.to]+=val;
flow[now]+=val;
if(over[p]==0)
return;
}
now=net[now].next;
}
}
void remark(int p)
{
int minh=INF;
int now=p;
while(now!=-1)
{
edge v=net[now].val;
if(flow[now]<v.cap)
minh=min(minh,h[v.to]);
now=net[now].next;
}
h[p]=minh+1;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d%d",&s,&t);
for(int i=1;i<=n;i++)
if(i!=s && i!=t)
net[i]={{s,INF},-1};
net[s]={{n+1,0},-1};
m+=n;
int last[10001];
for(int i=1;i<=n;i++)
last[i]=i;
for(int i=n+1;i<=m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
if(b==s || a==t || a==b)
continue;
net[last[a]].next=i;
last[a]=i;
net[i]={{b,w},-1};
}
int now=s;
while(now!=-1)
{
if(net[now].val.to==n+1)
{
now=net[now].next;
continue;
}
edge v=net[now].val;
flow[now]=v.cap;
over[v.to]=v.cap;
if(v.to!=t)
overflow.push(v.to);
now=net[now].next;
}
h[s]=n;
while(!overflow.empty())
{
int p=overflow.front();
overflow.pop();
while(true)
{
int before=over[p];
push(p);
int after=over[p];
if(before==after)
remark(p);
if(after==0)
break;
}
}
printf("%d\n",over[t]);
return 0;
}
码风清奇,请见谅QwQ