enor2017 @ 2018-12-01 21:45:58
我照着题解看了好几遍了…………
还是没发现哪出问题了,十个点全TLE
求助
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cctype>
using namespace std;
typedef int ll;
const ll INF=1LL<<30;
const ll MAXN=1e4+50;
const ll EMAXN=1e5+50;
void read(ll &x){
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
}
ll n,m,s,t;
ll head[MAXN],cnt=1;
struct EDGE{
ll to,next,wei;
}e[EMAXN*2];
ll dep[MAXN];
bool vis[MAXN];
void addedge(ll u,ll v,ll wei){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].wei=wei;
}
bool bfs(){
fill(dep,dep+MAXN-1,INF);
memset(vis,false,sizeof(vis));
queue<ll> q;
q.push(s);
dep[s]=0;
//vis[s]=true;
while(!q.empty()){
ll now=q.front();
q.pop();
vis[now]=false;
for(ll i=head[now];i;i=e[i].next){
ll v=e[i].to;
if(dep[v]>dep[now]+1&&e[i].wei){
dep[v]=dep[now]+1;
if(!vis[v]){
q.push(v);
vis[v]=true;
}
}
}
}
if(dep[t]!=INF) return true;
else return false;
}
ll dfs(ll u,ll flow){
ll thisflow=0;
if(u==t) return flow;
for(ll i=head[u];i;i=e[i].next){
ll v=e[u].to;
if(e[i].wei&&dep[v]==dep[u]+1){
if((thisflow=dfs(v,min(flow,e[i].wei)))){
e[i].wei-=thisflow;
e[i^1].wei+=thisflow;
return thisflow;
}
}
}
return 0;
}
ll maxflow=0;
ll dinic(){
ll lowflow;
while(bfs()){
while(lowflow=dfs(s,INF))maxflow+=lowflow;
}
return maxflow;
}
int main(){
read(n),read(m),read(s),read(t);
ll x,y,z;
for(ll i=1;i<=m;++i){
read(x),read(y),read(z);
addedge(x,y,z);
addedge(y,x,0);
}
cout<<dinic()<<endl;
//printf("%lld\n",dinic());
return 0;
}
by GK0328 @ 2018-12-01 21:55:35
@enor2017
by enor2017 @ 2018-12-01 21:56:19
@可口可乐头
by enor2017 @ 2018-12-01 21:56:50
by enor2017 @ 2018-12-01 21:57:00
by 紬文德斯 @ 2018-12-01 21:57:02
@enor2017 2333~~ @可口可乐头 的是正解
by GK0328 @ 2018-12-01 21:57:08
@enor2017 我可菜了QAQ
by enor2017 @ 2018-12-01 21:58:21