• 应用
• 登录
• 注册

# 70分WA3点求好心dalao查错

@henry_y 2018-03-13 22:58 回复
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll int
#define M 100100
#define N 10010
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
#define abs(x) x>0?x:-x
#define mod 10000007
inline void read(ll &x){x=0;ll f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
using namespace std;
struct edge{ll to,next,v;}e[M<<1];
ll q[N],h[N];//q为队列，h为分层
ll n,m,s,t;
inline void add(ll u,ll v,ll w){
}//邻接表
inline bool bfs(){//划分层次
ll l=0,r=1,now,i;
mt(h,-1);q[0]=s;h[s]=0;
while(l!=r){
now=q[l++];
if(e[i].v&&h[e[i].to]==-1){
h[e[i].to]=h[now]+1;
q[r++]=e[i].to;
}
}
}
return h[t]!=-1;
}
inline ll dfs(ll x,ll f){//找增广路
if(x==t)return f;
ll w,i,used=0;
if(h[e[i].to]==h[x]+1&&e[i].v){
w=dfs(e[i].to,min(f-used,e[i].v));
used+=w;e[i].v-=w;e[i^1].v+=w;
if(used==f)return f;
}
}
if(!used)h[x]=-1;
return used;
}
inline ll dinic(){
ll ans=0;
while(bfs())ans+=dfs(s,inf);
return ans;
}
int main(){
for(ll i=1;i<=m;i++){
}
printf("%d",dinic());
return 0;
}


WA3个点，好心的dalao查查错？

@henry_y 2018-03-13 23:01 回复

10 25 2 10
3 4 4
4 3 45
3 5 80
1 6 94
3 7 63
9 8 92
1 9 75
6 3 12
7 9 63
6 1 39
6 1 97
9 7 33
7 4 55
8 9 36
5 2 61
9 8 97
2 4 36
1 2 2
10 2 14
5 9 82
5 1 32
6 2 94
9 2 10
6 10 50
7 6 53


36

178