1 条题解
-
0
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define N 2010 #define K 210 #define M 100010 #define inf 0x7fffffff/2 using namespace std; typedef long long ll; typedef unsigned long long ull; inline ll read() { char ch=getchar(); ll s=0,w=1; while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } struct edge { int next,to,fl,v; }e[M<<1]; int head[N],cnt=1; int n,m; int dist[N],pre[N],wch[N]; //pre表示spfa中每个点是从哪条边来的,wch表示spfa中每个点是从哪个点来的 queue<int>Q; int vis[N]; int c[K][K];//第i辆车被第j格师傅修所花的时间 int s,t; int minn[N];//minn表示spfa中s到每个点所经过的边中的最小流量 inline void add_edge(int from,int to,int fl,int v) { e[++cnt].to=to; e[cnt].next=head[from]; e[cnt].v=v; e[cnt].fl=fl; head[from]=cnt; }//加边 void dfs(int now,int sub) { e[wch[now]].fl-=sub; e[wch[now]^1].fl+=sub; if(pre[now])dfs(pre[now],sub); }//修改流量 inline int spfa() { for(register int i=1;i<=t;i++)dist[i]=inf; memset(vis,0,sizeof(vis));while(!Q.empty())Q.pop(); Q.push(s),vis[s]=1;minn[s]=inf;//不要忘了给minn[s]设初值 while(!Q.empty()) { int x=Q.front();Q.pop();vis[x]=0; for(register int i=head[x];i;i=e[i].next) { if(dist[e[i].to]>dist[x]+e[i].v&&e[i].fl>0) { dist[e[i].to]=dist[x]+e[i].v; wch[e[i].to]=i;pre[e[i].to]=x; minn[e[i].to]=min(minn[x],e[i].fl); if(!vis[e[i].to]) { Q.push(e[i].to); vis[e[i].to]=1; } } } } if(dist[t]==inf)return inf;//如果从s到不了t了 dfs(t,minn[t]);//修改边的流量 return minn[t]*dist[t]; }//最短路 inline int EK() { int sum=0; while(1) { int x=spfa(); if(x==inf)return sum;//没有增广路了 else sum+=x; } } int main() { m=read(),n=read(); t=n*m+n+1; for(register int i=1;i<=n;i++) { for(register int j=1;j<=m;j++){c[i][j]=read();} } for(register int i=1;i<=n*m;i++) { add_edge(s,i,1,0);add_edge(i,s,0,0); } for(register int i=1;i<=m;i++) { for(register int j=1;j<=n;j++) { for(register int k=1;k<=n;k++) { int now=(i-1)*n+k; add_edge(now,j+n*m,1,c[j][i]*k); add_edge(j+n*m,now,0,-c[j][i]*k); } } } for(register int i=1;i<=n;i++)add_edge(n*m+i,t,1,0),add_edge(t,n*m+i,0,0); printf("%.2lf",double(double(EK())/double(n))); return 0; //我的建图方式可能和前面我的题解写的方式不大一样,代码中我是师傅练得源点,车连的汇点 }
- 1
信息
- ID
- 1070
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 39
- 已通过
- 17
- 上传者