|
Posted on 2010-10-13 23:23 Uriel 阅读(237) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 网络流
网络流一拖再拖,发现再不临时抱佛脚一下Regional我们队要悲剧了。。= =。。于是刚看了几天最大流。。 看某分类说这题是最大流,但是这题AC甚少,看到Discuss说很裸于是看了题,但是题目中的约束条件:至多有1个server不满流 不知道怎么办。于是搜了下解题报告, http://blog.sina.com.cn/s/blog_64675f540100jz9x.html 很犀利 Orz 然后建图就很简单了,一个公共源点流向每个application,流量上限就是每个application需要的CPU数,然后每个application能在哪些server上运行就连边,流量上限也是该application所需的CPU数,所有的server流向公共汇点。 然后开始模板,用的是ISAP 这题还要输出具体的流向情况,因为我模板用的是前向星,感觉单纯记录边还是不太方便,在前向星中增加了一个记录弧尾的数组,然后再开一个邻接矩阵,在ISAP中调整流量的时候顺便记录 。 加读入输出优化63MS,马马虎虎的速度。暂时没想到什么更好的方法,欢迎大牛们指教。 附上又臭又长的代码一份:
//Problem: 3759 User: Uriel
//Memory: 1296K Time: 63MS
//Language: G++ Result: Accepted

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 405
#define M 80810
#define inf 0x7fffffff
#define min(a,b) (a<b?a:b)

int adj[N][N];
int eu[M],ev[M],nxt[M],cur[M],pre[N],flag[N],head[N],d[N],vd[N],e,n,m,g[M];
int src,sink;

 int in() {
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
 while((ch=getchar())!=' ' && ch!='\n' && ch<='9' && ch>='0') {
a*=10;
a+=ch-'0';
}
return a;
}

 void out(int a) {
if(a>=10)out(a/10);
putchar(a%10+'0');
}

 void addedge(int u,int v,int w) {
eu[e]=u;ev[e]=v;g[e]=w;nxt[e]=head[u];head[u]=e++;
eu[e]=v;ev[e]=u;g[e]=0;nxt[e]=head[v];head[v]=e++;
}

 int aug(int pre[],int flag[]) {
int i,s=inf;
for(i=sink;i!=src;i=pre[i])s=min(s,g[flag[i]]);
 for(i=sink;i!=src;i=pre[i]) {
g[flag[i]]-=s,g[flag[i]^1]+=s;
adj[eu[flag[i]]][ev[flag[i]]]-=s;
adj[eu[flag[i]^1]][ev[flag[i]^1]]+=s;
}
return s;
}

 int ISAP() {
int now,ans=0,p,v;
cur[now=src]=head[src];
vd[d[sink]=0]=n;
 while(d[src]<n) {
if(now==sink)ans+=aug(pre,flag),now=src;
 for(p=cur[now];~p;p=nxt[p]) {
v=ev[p];
 if(g[p] && d[now]==d[v]+1) {
cur[now]=p;
break;
}
}
if(~p)pre[v]=now,flag[v]=p,now=v;
 else {
cur[now]=head[now];
if(!(--vd[d[now]]))break;
++vd[++d[now]];
if(now!=src)now=pre[now];
}
}
return ans;
}


 int main() {
int cap[205],np[205][205];
int nn,mm,i,j,k,a,x,y;
nn=in();mm=in();
e=0;
 for(i=0;i<=nn+mm+2;++i) {
head[i]=-1;
d[i]=vd[i]=0;
for(j=0;j<=nn+mm+2;++j)adj[i][j]=0;
}
 for(i=0;i<nn;++i) {
cap[i]=in();
addedge(0,i+1,cap[i]);
}
 for(i=0;i<mm;++i) {
x=in();
addedge(nn+1+i,nn+mm+1,x);
np[i][0]=in();
 for(k=1;k<=np[i][0];++k) {
np[i][k]=in();
++np[i][k];
addedge(np[i][k],1+nn+i,x);
}
}
src=0;sink=nn+mm+1;n=sink+1;
out(ISAP());
puts("");
 for(i=0;i<mm;i++) {
if(!np[i][0])continue;
out(adj[i+nn+1][np[i][1]]);
 for(j=2;j<=np[i][0];++j) {
putchar(' ');
out(adj[i+nn+1][np[i][j]]);
}
puts("");
}
return 0;
}
|