|
|
Posted on 2010-10-13 23:23 Uriel 阅读(223) 评论(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;
}
|