http://poj.org/problem?id=3686
题意：
给定n个玩具，有m个车间，给出每个玩具在每个车间的加工所需的时间mat[i][j]表示第i个玩具在第j个车间加工所需的时间，规顶只有第i个玩具在j车间完成时第j车间才能接受其他玩具来生产。求加工完毕所有的的n个玩具所需的最小的平均时间。
思路：
不论使用KM求最小权匹配还是使用最小费用最大流求解，建图还是最重要的。笨啊...想不到啊。。
假设有n件玩具都在第j个车间生产，他们所需要的时间分别为T1 + 2*T1 + 3*T1 +..... + n*T1; 则第c个在j上的的所需时间为c*j，
我们将每个车间分成n个点，表示第i个可能是第几个在j车间上生产。然后求一个最小权匹配，或mcmf （这里注意好好计算边与点的数量）；
KM：
View Code #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll long long #define inf 0x7f7f7f7f #define MOD 1073741824 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 2555 #define N 55 using namespace std; //freopen("data.in","r",stdin);int w[N][M],mat[N][N]; int lx[N],ly[M],slack[M]; bool vtx[N],vty[M]; int lk[M]; int n,m;bool dfs(int i){vtx[i] = true;for (int j = 1; j <= m; ++j){if (vty[j]) continue;int tmp = lx[i] + ly[j] - w[i][j];if (tmp == 0){vty[j] = true;if (lk[j] == -1 || dfs(lk[j])){lk[j] = i;return true;}}else{slack[j] = min(slack[j],tmp);}}return false; } double KM(){int i,j;for (i = 1; i <= n; ++i){for (j = 1,lx[i] = -inf; j <= m; ++j){lx[i] = max(lx[i],w[i][j]);}}for (i = 1; i <= m; ++i){lk[i] = -1;ly[i] = 0;}for (i = 1; i <= n; ++i){for (j = 1; j <= m; ++j) slack[j] = inf;while (1){for (j = 1; j <= n; ++j) vtx[j] = false;for (j = 1; j <= m; ++j) vty[j] = false;if (dfs(i)) break;int d = inf;for (j = 1; j <= m; ++j){if (!vty[j]) d = min(d,slack[j]);}for (j = 1; j <= n; ++j){if (vtx[j]) lx[j] -= d;}for (j = 1; j <= m; ++j){if (vty[j]) ly[j] += d;else slack[j] -= d;}}}double sum = 0;for (i = 1; i <= m; ++i){if (lk[i] > -1) sum += w[lk[i]][i];}return (-sum); } int main(){//freopen("data.in","r",stdin);int i,j;int k;int T;scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);for (i = 1; i <= n; ++i){for (j = 1; j <= m; ++j){scanf("%d",&mat[i][j]);}}CL(w,0);for (i = 1; i <= n; ++i){for (j = 1; j <= m; ++j){for (k = 1; k <= n; ++k){w[i][(j - 1)*n + k] = -mat[i][j]*k;}}}m = n*m;double ans = KM()/(1.0*n);// printf("<>>>>>>>>>>>%d\n",m);printf("%.6lf\n",ans);}return 0; }
mcmf：
View Code #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll long long #define inf 0x7f7f7f7f #define MOD 1073741824 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 127566 #define N 53 using namespace std; //freopen("data.in","r",stdin);struct node{int v;int w,c;int next; }g[M*2]; int head[N*N],ct; int mat[N][N]; int pre[M],dis[M]; int path[M]; bool vt[M]; int n,m;void spfa(int s,int e){int i;for (i = s; i <= e; ++i){dis[i] = inf;pre[i] = -1;vt[i] = false;path[i] = 0;}pre[s] = s; dis[s] = 0;vt[s] = true;queue<int>q;q.push(s);while (!q.empty()){int u = q.front(); q.pop();for (int i = head[u]; i != -1; i = g[i].next){int v = g[i].v;int w = g[i].w;int ci = g[i].c;if (dis[v] > dis[u] + w && ci > 0){dis[v] = dis[u] + w;pre[v] = u;path[v] = i;if (!vt[v]){q.push(v);vt[v] = true;}}}vt[u] = false;} } double mcmf(int s,int e){double ans = 0;int i;while (1){spfa(s,e);if (pre[e] == -1) break;int MIN = inf;for (i = e; i != s; i = pre[i]){MIN = min(MIN,g[path[i]].c);}for (i = e; i != s; i = pre[i]){g[path[i]].c -= MIN;g[path[i]^1].c += MIN;ans += MIN*g[path[i]].w;}}return ans; } void add(int u,int v,int c,int w){g[ct].v = v;g[ct].c = c;g[ct].w = w;g[ct].next = head[u];head[u] = ct++; }int main(){//freopen("data.in","r",stdin);int i,j,T;int k;scanf("%d",&T);while (T--){CL(head,-1); ct = 0;scanf("%d%d",&n,&m);for (i = 1; i <= n; ++i){for (j = 1; j <= m; ++j){scanf("%d",&mat[i][j]);}}for (i = 1; i <= n; ++i){for (j = 1; j <= m; ++j){for (k = 1; k <= n; ++k){int tp = j*n + k;add(i,tp,1,mat[i][j]*k);add(tp,i,0,-mat[i][j]*k);/*c[i][tp] = 1; c[tp][i] = 0;w[i][tp] = mat[i][j]*k;w[tp][i] = -mat[i][j]*k;*/}}}int s = 0 , e = (m + 1)*n + 1;for (i = 1; i <= n; ++i){add(s,i,1,0); add(i,s,0,0);/*c[s][i] = 1; c[i][s] = 0;w[s][i] = w[i][s] = 0;*/}for (i = n + 1; i <= (m + 1)*n; ++i){add(i,e,1,0); add(e,i,0,0);/*c[i][e] = 1; c[e][i] = 0;w[i][e] = w[e][i] = 0;*/}printf("%.6lf\n",mcmf(s,e)/n);}return 0; }
