LordLeft @ 2019-12-17 18:59:10
RT,这个代码可以过预留推进的板子,但是过不了这个题,就很诡异
求dalao帮忙看一下
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
using namespace std;
int read(){
int w=0;
bool s=0;
char c=getchar();
while(!isdigit(c)){
s=(c=='-');
c=getchar();
}
while(isdigit(c)){
w=w*10+c-'0';
c=getchar();
}
return s?-w:w;
}
const int N=200005,M=3000005,inf=2147483647;
int n,m,S,T,ans;
struct Graph{
#define Ed Graph::Edge
struct Edge{
int to,flow;
Edge *nxt,*ops;
};
Edge e[M<<1],*head[N];
int cnt;
void add_for(int u,int v,int w){
e[++cnt]=(Edge){v,w,head[u],((cnt&1)?&e[cnt+1]:&e[cnt-1])};
head[u]=&e[cnt];
}
void add(int u,int v,int w){
add_for(u,v,w);
add_for(v,u,0);
}
void reset(int s){
for(int i=1;i<=s;i++){
head[i]=NULL;
}
cnt=0;
}
};
Graph G;
int h[N],gap[N<<1],sto[N];
bool vis[N];
struct cmp{
bool operator ()(int a,int b)const{
return h[a]<h[b];
}
};
priority_queue<int,vector<int>,cmp>p_que;
queue<int>que;
bool BFS(){
for(int i=1;i<=n;i++){
h[i]=inf;
}
h[T]=0;
que.push(T);
while(!que.empty()){
int u=que.front();
que.pop();
for(Ed *i=G.head[u];i!=NULL;i=i->nxt){
int v=i->to;
if((i->ops)->flow&&h[v]>h[u]+1){
h[v]=h[u]+1;
que.push(v);
}
}
}
return h[S]!=inf;
}
void push(int u){
for(Ed *i=G.head[u];i!=NULL&&sto[u];i=i->nxt){
int v=i->to;
if(i->flow&&h[v]+1==h[u]){
int flow=min(sto[u],i->flow);
i->flow-=flow;
(i->ops)->flow+=flow;
sto[u]-=flow;
sto[v]+=flow;
if(v!=S&&v!=T&&!vis[v]){
p_que.push(v);
vis[v]=1;
}
}
}
}
void relabel(int u){
h[u]=inf;
for(Ed *i=G.head[u];i!=NULL;i=i->nxt){
int v=i->to;
if(i->flow&&(h[v]+1<h[u])){
h[u]=h[v]+1;
}
}
}
int HLPP(){
if(!BFS()){
return 0;
}
h[S]=n;
for(int i=1;i<=n;i++){
if(h[i]!=inf){
gap[h[i]]++;
}
}
for(Ed *i=G.head[S];i!=NULL;i=i->nxt){
int v=i->to;
if(i->flow){
int flow=i->flow;
i->flow-=flow;
(i->ops)->flow+=flow;
sto[S]-=flow;
sto[v]+=flow;
if(v!=S&&v!=T&&!vis[v]){
p_que.push(v);
vis[v]=1;
}
}
}
while(!p_que.empty()){
int u=p_que.top();
p_que.pop();
vis[u]=0;
push(u);
if(sto[u]){
gap[h[u]]--;
if(!gap[h[u]]){
for(int v=1;v<=n;v++){
if(v!=S&&v!=T&&h[v]>h[u]&&h[v]<n+1){
h[v]=n+1;
}
}
}
relabel(u);
gap[h[u]]++;
p_que.push(u);
vis[u]=1;
}
}
return sto[T];
}
int main(){
n=read(),m=read(),S=read(),T=read();
G.reset(n);
for(int i=1;i<=m;i++){
int u,v,w;
u=read(),v=read(),w=read();
G.add(u,v,w);
}
ans=HLPP();
printf("%d\n",ans);
return 0;
}
by 辰星凌 @ 2019-12-17 19:01:26
ORZ网络瘤巨佬
by ACAね @ 2019-12-17 19:30:43
@LordLeft Orz
by qian_shang @ 2019-12-17 19:40:22
@LordLeft 网络流?我来我来,指针?算了算了