Posted on 2010-10-13 23:23
Uriel 閱讀(258)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
網(wǎng)絡(luò)流
網(wǎng)絡(luò)流一拖再拖，發(fā)現(xiàn)再不臨時抱佛腳一下Regional我們隊要悲劇了。。= =。。于是剛看了幾天最大流。。
看某分類說這題是最大流，但是這題AC甚少，看到Discuss說很裸于是看了題，但是題目中的約束條件：至多有1個server不滿流 不知道怎么辦。于是搜了下解題報告，
http://blog.sina.com.cn/s/blog_64675f540100jz9x.html 很犀利 Orz
然后建圖就很簡單了，一個公共源點(diǎn)流向每個application，流量上限就是每個application需要的CPU數(shù)，然后每個application能在哪些server上運(yùn)行就連邊，流量上限也是該application所需的CPU數(shù)，所有的server流向公共匯點(diǎn)。
然后開始模板，用的是ISAP
這題還要輸出具體的流向情況，因為我模板用的是前向星，感覺單純記錄邊還是不太方便，在前向星中增加了一個記錄弧尾的數(shù)組，然后再開一個鄰接矩陣，在ISAP中調(diào)整流量的時候順便記錄 。
加讀入輸出優(yōu)化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;
}