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 紬文德斯 @ 2018-12-01 21:50:20
fill是什么鬼= =
要不要我的码风优良常数较小的模板QAQ
by enor2017 @ 2018-12-01 21:51:03
@紬文德斯 我的INF
写成这样之后就不能用memset
了好慌啊
by 紬文德斯 @ 2018-12-01 21:52:14
@enor2017 哦哦这个意思啊QAQ
你memset 0x3f 或 7f 不就行了嘛QAQ
我帮你再看看
by decoqwq @ 2018-12-01 21:52:33
感觉dfs问题大了吧。。
by enor2017 @ 2018-12-01 21:53:33
@Decoration
by GK0328 @ 2018-12-01 21:54:00
@enor2017 SPFA?
by GK0328 @ 2018-12-01 21:54:41
ll v=e[u].to;
@enor2017
by enor2017 @ 2018-12-01 21:54:59
@可口可乐头 额……只是dinic
的最大流
by GK0328 @ 2018-12-01 21:55:06
仔细看看这是啥
by GK0328 @ 2018-12-01 21:55:28
你确定不是e[i].to