說一下題意：有一個小女孩從小就夢想成為一名影星，現在機會來了，有很多電影公司找她拍電影，但是這些拍電影的日程安排之間可能還有沖突，但是有女孩不想錯過任何機會，想把每個公司的電影都接下來，但是她不知道能不能接下所有的電影，所有找到了你優秀的ACMER來幫忙解決問題。
數據的輸入如下：有T組數據每組先有一個N表示要找她拍的電影的個數，其中N<=20;
每個電影有9個數據，前7個數據表示一個星期的7天 ，這7個數不是0，就是1，1表示能在這天拍電影，0表示不能在這天拍電影 還有2個數據D,W
D表示這部電影需要她拍D天才能完成，W表示這D天必須在前W周內。ok題意就是這樣，下面考慮該怎樣建圖
***************************************
每部電影作為一個源點，然後把每個星期的每一天看成一個點，每個點只可以貢獻一個工作日，即出邊（到匯點）的容量只能是1，而入邊的容量也為1，只要某部電影可以在該天工作，就可能選擇該天，即該部電影對應的點到該個工作日對應的點之間連一條線，最後，添加一個超級源點，它到每部電影對於的點之間的容量為該部電影需要的工作日（不能為無窮大）
*****************************************
ok 圖建完了就簡單了只用判最大流是不是等於要拍的所有電影的天數的和，若等於就輸出Yes,不然就輸出No
這題我也是用的上一題的代碼稍微改了一下，建圖部分就出來了
代碼如下：
/********* PRO: POJ 1698 TIT: Alice's Chance DAT: 2013-08-12 AUT: UKean EMA: [email protected] *********/ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define INF 1e9 using namespace std; queue<int> que;//廣搜需要使用的隊列 int M;//M是點數 int s,t;//源點和匯點 int flow[405][405];//殘流量 int p[405];//廣搜記錄路徑的父節點數組 int a[405];//路徑上的最小殘量 int cap[405][405];//容量網絡 int ans;//最大流 int data[30][10];//存讀入數據的部分 int sum;//存拍所有電影需要的天數 int read() { int flim_num;cin>>flim_num; for(int i=0;i<flim_num;i++) for(int j=0;j<9;j++) cin>>data[i][j]; s=0;t=1;//源點匯點 for(int i=M=0;i<flim_num;i++) M=max(data[i][8],M); M=M*7+30;//算出大概的總的點數 memset(cap,0,sizeof(cap)); //2 --21 是電影,22後面的點表示時間 for(int i=2;i<flim_num+2;i++) cap[0][i]=data[i-2][7];//超級源點到每個電影的邊 //處理電影到每天 for(int i=0;i<flim_num;i++) for(int j=0;j<7;j++)//j是一周的第幾天 if(data[i][j]==1) for(int k=0;k<data[i][8];k++)//k是第幾周 { cap[i+2][k*7+j+22]=1;//電影到第幾天的邊的容量 cap[k*7+j+22][1]=1;//第幾天到匯點的邊的容量 } sum=0; for(int i=0;i<flim_num;i++) sum+=data[i][7];//計算出拍完所有的電影需要的天數 return 1; } int deal()//增廣路算法 { memset(flow,0,sizeof(flow)); ans=0; while(1) { memset(a,0,sizeof(a)); a[s]=INF; que.push(s); while(!que.empty()) { int u=que.front();que.pop(); for(int v=1;v<=M;v++) if(!a[v]&&cap[u][v]-flow[u][v]>0) { p[v]=u; que.push(v); a[v]=min(a[u],cap[u][v]-flow[u][v]);//路徑上的最小殘流量 } } if(a[t]==0) break; for(int u=t;u!=s;u=p[u]) { flow[p[u]][u]+=a[t]; flow[u][p[u]]-=a[t]; } ans+=a[t]; } //cout<<ans<<endl; return ans; } int main() { int T;cin>>T; while(T--) { read(); if(deal()==sum) puts("Yes"); else puts("No"); } return 0; }
