【洛谷2053】 [SCOI2007]修车（费用流）

浅浅的花香味﹌ 2021-12-20 02:25 175阅读 0赞

## 传送门 ##

[洛谷][Link 1]

## Solution ##

考虑把每一个修车工人拆成\\(n\\)个点，那么考虑令\\(id(i,j)\\)为第\\(i\\)个工人倒数第\\(j\\)次修车。  
然后就可以直接跑费用流了！！！

## 代码实现 ##

/* mail: mleautomaton@foxmail.com author: MLEAutoMaton This Code is made by MLEAutoMaton */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<set> #include<map> #include<iostream> using namespace std; #define ll long long #define re register #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout) inline int gi() { int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum; } int m,n,s,t,T[110][110]; queue<int>Q; const int N=500010,M=2000010,Inf=1e9+10; struct node { int to,nxt,w,c; }e[M<<1]; int front[N],cnt,dis[N],vis[N],fa[N],from[N]; void Add(int u,int v,int flow,int cost) { e[cnt]=(node){v,front[u],flow,cost};front[u]=cnt++; e[cnt]=(node){u,front[v],0,-cost};front[v]=cnt++; } bool SPFA() { memset(dis,63,sizeof(dis)); Q.push(s);dis[s]=0; while(!Q.empty()) { int u=Q.front();Q.pop();vis[u]=0; for(int i=front[u];i!=-1;i=e[i].nxt) { int v=e[i].to; if(e[i].w && dis[v]>dis[u]+e[i].c) { dis[v]=dis[u]+e[i].c;fa[v]=u,from[v]=i; if(!vis[v])Q.push(v),vis[v]=1; } } } return dis[t]!=dis[t+1]; } int McMf() { int cost=0; while(SPFA()) { int di=Inf; for(int i=t;i!=s;i=fa[i])di=min(di,e[from[i]].w); cost+=di*dis[t]; for(int i=t;i!=s;i=fa[i]) e[from[i]].w-=di,e[from[i]^1].w+=di; } return cost; } int main() { #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); #endif m=gi();n=gi(); memset(front,-1,sizeof(front)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) T[i][j]=gi(); for(int i=1;i<=n;i++) Add(s,i,1,0); t=n*m+n+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) Add(i,(j-1)*n+k+n,1,k*T[i][j]); for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) Add((j-1)*n+i+n,t,1,0); printf("%.2lf\n",(double)(McMf()*1./n)); return 0; }

转载于:https://www.cnblogs.com/mle-world/p/10552375.html

[Link 1]: https://www.luogu.org/problemnew/show/P2053