社区讨论
为什么不开O2就会RE?
P1345[USACO5.4] 奶牛的电信 Telecowmunication参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lobff3fi
- 此快照首次捕获于
- 2023/10/29 20:07 2 年前
- 此快照最后确认于
- 2023/11/04 01:39 2 年前
不开O2就会RE,求助大佬
CPP#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=2e6+5;
int n,m,s,t,ans,dep[N],now[M];
int first[N],nex[M],to[M],w[M],tot=1;
void add(int x,int y,int z)
{
nex[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
int dfs(int x,int flow)
{
if(x==t) return flow;
int rest=flow,i,k;
for(int i=now[x];i&&rest;i=nex[i])
{
int y=to[i];
if(w[i] && dep[y]==dep[x]+1)
{
k=dfs(y,min(rest,w[i]));
if(!k) dep[y]=0;
w[i]-=k;
w[i^1]+=k;
rest-=k;
}
}
now[x]=i;
return flow-rest;
}
bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int>a;
a.push(s);dep[s]=1;now[s]=first[s];
while(!a.empty())
{
int x=a.front();a.pop();
for(int i=first[x];i;i=nex[i])
{
int y=to[i];
if(w[i] && dep[y]==0)
{
a.push(y);
now[y]=first[y];
dep[y]=dep[x]+1;
if(y==t) return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
s+=n;
for(int i=1;i<=n;i++)
{
add(i,i+n,1);
add(i+n,i,0);
}
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(y+n,x,0x3f3f3f3f);
add(x,y+n,0);
add(x+n,y,0x3f3f3f3f);
add(y,x+n,0);
}
int flow=0;
while(bfs())
while(flow=dfs(s,0x3f3f3f3f)) ans+=flow;
cout<<ans;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...