标签：efi lin for nbsp pop ack tmp push 一个
题目:
给n个订单和m个车间,每个车间对于每个订单有一个处理时间,一个车间只能同时且完全处理一个车间
问最小平均时间
题解:
考虑把车间拆点,对于每个时间的车间拆开,这样对于第i个订单来说,他在第j个车间被倒数第k个处理就要花费k*z[i][j]的时间
建图:
1.S向每个任务连w=1,c=0边
2.每个任务向每个被拆开的车间连 w=1,c=k*z[i][j]的边
3.每个被拆开的车间向汇点连w=1,c=0边
#include
#include
#include
#include
#define N 1010
#define INF 1000000000
using namespace std;
int ecnt=1,vis[N*N],dist[N*N],n,m,S,T,ans,head[N*N],test,z[N][N],tot;
deque q;
struct adj
{
int nxt,v,w,c;
}e[1000010];
inline void add(int u,int v,int w,int c)
{
e[++ecnt].v=v,e[ecnt].w=w,e[ecnt].c=c,e[ecnt].nxt=head[u],head[u]=ecnt;
e[++ecnt].v=u,e[ecnt].w=0,e[ecnt].c=-c,e[ecnt].nxt=head[v],head[v]=ecnt;
}
inline int spfa(int s,int t)
{
int v;
memset(vis,0,sizeof(vis));
for (int i=S;i0 && dist[v=e[i].v]>dist[u]-e[i].c)
{
dist[v]=dist[u]-e[i].c;
if (!vis[v])
{
vis[v]=1;
if (!q.empty() && dist[v]0 && dist[x]-e[i].c==dist[v])
{
tmp=dfs(v,min(e[i].w,flow-used));
if (tmp>0)
ans+=tmp*e[i].c,e[i].w-=tmp,e[i^1].w+=tmp,used+=tmp;
if (used==flow) break;
}
return used;
}
inline int CostFlow()
{
int Flow=0;
while (spfa(S,T))
{
vis[T]=1;
while (vis[T])
{
memset(vis,0,sizeof(vis));
Flow+=dfs(S,INF);
}
}
return Flow;
}
void init()
{
memset(head,0,sizeof(head));
ecnt=1;
S=0,T=n*m+n+1;
ans=0;
}
int main()
{
scanf("%d",&test);
while (test--)
{
scanf("%d%d",&n,&m);
init();
for (int i=1;i
POJ 3686 The Windy's | 最小费用最大流
标签：efi lin for nbsp pop ack tmp push 一个
原文地址：http://www.cnblogs.com/mrsheep/p/7953669.html