社区讨论
错一个样例,求调
P1344[USACO4.4] 追查坏牛奶 Pollutant Control参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m43hzicp
- 此快照首次捕获于
- 2024/11/30 09:32 去年
- 此快照最后确认于
- 2025/11/04 13:38 4 个月前
CPP
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int M=1005,N=35;
struct node{
int v,c,ne;
}a[M<<1];
int n,m,idx=1,h[N],s[M],e[M],c[M],d[N],S,T,cur[N];
void add(int aa,int bb,int cc){
a[++idx]={bb,cc,h[aa]};
h[aa]=idx;
}
bool bfs(){
memset(d,0,sizeof d);
queue<int>q;
q.push(S);d[S]=1;
while(q.size()){
int u=q.front();q.pop();
for(int i=h[u];i;i=a[i].ne){
int v=a[i].v;
if(d[v]==0&&a[i].c){
d[v]=d[u]+1;
if(v==T) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int mf){
if(u==T) return mf;
int sum=0;
for(int i=cur[u];i;i=a[i].ne){
cur[u]=i;
int v=a[i].v;
if(d[v]==d[u]+1&&a[i].c){
int f=dfs(v,min(mf,a[i].c));
a[i].c-=f;
a[i^1].c+=f;
sum+=f;
mf-=f;
if(mf==0) break;
}
}
if(sum==0) d[u]=0;
return sum;
}
int dinic(){
int f=0;
while(bfs()){
memcpy(cur,h,sizeof h);
f+=dfs(S,1e9);
}
return f;
}
int main(){
scanf("%d%d",&n,&m);
S=1,T=n;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&s[i],&e[i],&c[i]);
add(s[i],e[i],c[i]);
add(e[i],s[i],0);
}
printf("%d ",dinic());
idx=1;
memset(h,0,sizeof h);
for(int i=1;i<=m;i++){
add(s[i],e[i],1);
add(e[i],s[i],0);
}
printf("%d",dinic());
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...