POJ-3686[The Windy's]最小費用フローまたはKM

題意:N個のタスクとM個のマシンがあり、i個目のタスクがj個目のマシンで完了する時間map[i][j]を与え、各マシンは同じ時刻に1つのタスクしか処理できず、マシンは1つのタスクを完全に完了してから次のタスクを完了しなければならない.N個の任務の完成時間の平均値は最低でいくらですかを聞きます.
キー:N個のタスクの実行時間をそれぞれT 1,T 2…TNとすると、N個のオーダーの総実行時間はT 1＊N＋T 2＊(N−1)＋…＋TN−1＊2＋TNである.
構図:各機器をN点に分解する.k番目のポイントは、最後からk番目に完了したタスクを表します.タスクiとマシンjのk番目のポイントをmap[i][j]*kのエッジに結合する.総点数:N+M*N+2;
総辺数:(N+N*M+N*M)*2;
PS.この問題は比較的良い構図問題です.費用フローの効率は低いが、KMはまだ見ていないので、費用フローを使うしかない.
構図コード:

void Init()//  
{
	int i,j,k;
	memset(head,-1,sizeof(head));ecnt=0;
	scanf("%d%d",&N,&M);
	scr=0;sink=N+M*N+1;vn=sink+1;
	for(i=1;i<=N;i++)
		Insert(scr,i,1,0);
	for(i=N+1;i<=M*N+N;i++)
		Insert(i,sink,1,0);
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=M;j++)
		{
			scanf("%d",&map[i][j]);
			//Insert(i,j+N,1,map[i][j]);
		}
	}
	for(i=1;i<=N;i++)
	{
		int cnt=N+1;
		for(j=1;j<=M;j++)
		{
			for(k=1;k<=N;k++)
			{
				Insert(i,cnt++,1,map[i][j]*k);
			}
		}
	}
}

CODE:

/*     +  */
/*AC  ：969ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <queue>
#define MAXN 2600
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define INF 1e8
using namespace std;
struct edge
{
	int u,v,w,c,next;
}E[800000];
int head[MAXN],ecnt;
bool vis[MAXN];
int dis[MAXN],pre[MAXN];
int map[55][55];
int N,M,scr,sink,vn;

void Insert(int u,int v,int w,int c)
{
	E[ecnt].u=u;
	E[ecnt].v=v;
	E[ecnt].w=w;
	E[ecnt].c=c;
	E[ecnt].next=head[u];
	head[u]=ecnt++;
	E[ecnt].u=v;
	E[ecnt].v=u;
	E[ecnt].w=0;
	E[ecnt].c=-c;
	E[ecnt].next=head[v];
	head[v]=ecnt++;
}
void Init()//  
{
	int i,j,k;
	memset(head,-1,sizeof(head));ecnt=0;
	scanf("%d%d",&N,&M);
	scr=0;sink=N+M*N+1;vn=sink+1;
	for(i=1;i<=N;i++)
		Insert(scr,i,1,0);
	for(i=N+1;i<=M*N+N;i++)
		Insert(i,sink,1,0);
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=M;j++)
		{
			scanf("%d",&map[i][j]);
			//Insert(i,j+N,1,map[i][j]);
		}
	}
	for(i=1;i<=N;i++)
	{
		int cnt=N+1;
		for(j=1;j<=M;j++)
		{
			for(k=1;k<=N;k++)
			{
				Insert(i,cnt++,1,map[i][j]*k);
			}
		}
	}
}

queue<int>Q;
bool SPFA(int s,int t,int n)
{
	
	int i,u,v,c;
	memset(vis,false,sizeof(vis));
	for(i=0;i<=n;i++)
		dis[i]=INF;
	Q.push(s);
	pre[s]=-1;
	dis[s]=0;
	vis[s]=true;
	while(!Q.empty())
	{
		//printf("^
");
		u=Q.front();Q.pop();
		vis[u]=false;
		for(i=head[u];i!=-1;i=E[i].next)
		{
			v=E[i].v;c=E[i].c;
			if(E[i].w>0&&dis[v]>dis[u]+c)//   E[i].w>0
			{
				dis[v]=dis[u]+c;
				pre[v]=i;
				if(!vis[v])
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
	if(dis[t]<INF) return true;
	return false;
}

void Solve()
{
	int i,u,v,du,dv,ans=0,flow;
	while(SPFA(scr,sink,vn))
	{
		//printf("*
");
		ans+=dis[sink];
		for(i=pre[sink];i!=-1;i=pre[E[i].u])//    
		{
			E[i].w--;
			E[i^1].w++;
		}
	}
	double res=ans*1.0/N;
	printf("%.6lf
",res);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		Init();
		Solve();
	}
	return 0;
}