Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:绝对可以用，我就用费用流A了

Posted by 120106701 at 2017-01-25 16:54:00 on Problem 2112
In Reply To:这一题可以用最小费用最大流么？ Posted by:201226010211 at 2014-07-19 08:53:16
```距离做费用，然后把spfa约束条件改为更新费用最大值，增广时也这么更新

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=245,M=15000,inf=0x3f3f3f3f;
int m,n,cnt=1,K,T,C,h[N],pre[N],path[N],d[N],q[N],mp[N][N];
struct rec{int y,z,c,next;}e[M];bool inq[N];
inline void add(int x,int y,int z,int c){
e[++cnt].y=y,e[cnt].z=z,e[cnt].c=c,e[cnt].next=h[x],h[x]=cnt;
e[++cnt].y=x,e[cnt].z=0,e[cnt].c=-c,e[cnt].next=h[y],h[y]=cnt;
}
inline bool spfa(){
memset(d,inf,sizeof(d)),d[0]=0;
memset(inq,0,sizeof(inq));
int cl=1,op=0;q[0]=0,inq[0]=1;
while(cl!=op){
int x=q[op];op=(op+1)%N;
for(int i=h[x];i;i=e[i].next)
if(e[i].z && d[e[i].y]>max(d[x],e[i].c)){
d[e[i].y]=max(d[x],e[i].c);pre[e[i].y]=x,path[e[i].y]=i;
if(!inq[e[i].y])	q[cl]=e[i].y,cl=(cl+1)%N,inq[e[i].y]=1;
}
inq[x]=0;
}
return d[T]!=inf;
}
inline int ford_fulkerson(){
int ans=0;
while(spfa()){
ans=d[T];int minf=inf;
for(int i=T;i;i=pre[i])	minf=min(minf,e[path[i]].z);
for(int i=T;i;i=pre[i])	e[path[i]].z-=minf,e[path[i]^1].z+=minf;
}
return ans;
}
int main(){
scanf("%d%d%d",&K,&C,&m);n=K+C;T=n+1;
memset(mp,inf,sizeof(mp));for(int i=1;i<=n;i++)	mp[i][i]=0;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=n;j++){scanf("%d",&x);if(x) mp[i][j]=x;}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
for(int i=K+1;i<=n;i++)
printf("%d\n",ford_fulkerson());
return 0;
}```

Followed by: