●（做codevs1908時(shí)，發(fā)現(xiàn)測(cè)試數(shù)據(jù)也涵蓋了1907，想要一并做了，但因?yàn)椤凹夹g(shù)”不佳，搞了一上午）

●09方格取數(shù)問題（codevs1907? 方格取數(shù)3）

• 想了半天，也沒成功建好圖；
• 無(wú)奈下參考題解，說(shuō)是本題要求二分圖點(diǎn)權(quán)最大獨(dú)立集，然后可以由結(jié)論：“最大點(diǎn)權(quán)獨(dú)立集 = 所有點(diǎn)權(quán) - 最小點(diǎn)權(quán)覆蓋集 = 所有點(diǎn)權(quán) - 最小割集 = 所有點(diǎn)權(quán) - 網(wǎng)絡(luò)最大流”轉(zhuǎn)化到求最大流（我真的很懵逼，但又感覺很有道理）；
• 下面附上solution：（自己領(lǐng)悟吧）
• （不懂那個(gè)鬼結(jié)論的我就用那個(gè)結(jié)論建了個(gè)圖，跑了個(gè)Dinic。）

●13星際轉(zhuǎn)移問題（codevs 1908）

• （這個(gè)題的要比上一個(gè)好想一些。（因?yàn)樯弦活}的鬼結(jié)論我真不知道））
• 思路：
  • 本題的建圖比較有趣，要把每個(gè)空間站按天數(shù)進(jìn)行建點(diǎn)和連邊；
  • 建圖:
    • 1.原點(diǎn)（s）到地球（ear）有一條容量為k的邊；（表示要送出k個(gè)人民）
    • 2.月球（yue）到匯點(diǎn)（t）有一條容量為INF的邊；
    • 3.每個(gè)空間站的前一天的點(diǎn)到該空間站的后一天有一條容量為INF的邊；（表示人民可以待在空間站里度過一天又一天）
    • 4.若一個(gè)飛船在前一天在某一空間站（或地球），后一天在另一個(gè)空間站（或月球），則在對(duì)應(yīng)的兩個(gè)點(diǎn)間連一條有向邊，容量為飛船的載重；（表示前一天某一空間站（或地球）的幾個(gè)人民可以通過一個(gè)飛船坐到后一天的另一個(gè)空間站（或月球）；
  • 以題目的樣例為例，上一張圖幫助理解；
  • 上圖中：
    • 方框?yàn)辄c(diǎn)，里面的數(shù)字為編號(hào)；
    • 黑色箭頭為邊，上的數(shù)字為容量，（未標(biāo)的均為INF）；
    • 紅色路徑為最大的可行流。
  • （建圖方法解決后，但還有一個(gè)問題，Day是未知的，該怎么確定點(diǎn)有多少呢？）
  • 方法：枚舉天數(shù)或二分天數(shù)，然后跑個(gè)最大流判斷是否能將人民送完（即匯點(diǎn)的流入量是否等于k）；
  • 選擇：枚舉天數(shù)：
  • 原因：改圖比較特殊，若用枚舉天數(shù)的方法，只需每次在前一次的圖上加新點(diǎn)，連新邊即可，一直到找到答案。若用二分的話，則需要每次重新建圖。
  • （當(dāng)然，在開始枚舉天數(shù)之前，先用并查集檢查一下人民能否從地球到月球。）
  • 總：枚舉+Dinic（找最大流）+并查集（e，只是用來(lái)檢查的）

●代碼(為了AC掉codevs1908，把兩份代碼懟到一起了)：

#include<iostream> #include<cstdio> #include<cstring> #define INF 0x3f3f3f3f using namespace std; int n,m,k,yue=1,ear=2,sz=4,ent=2,aim,tot,s,t; int sps[30][30],cw[30][2],ld[30],ls[30],head[30000],h[30000],q[30000]; int fa[30]; struct edge{int to,cap,next; }e[300000]; bool special_read() {char s[100];gets(s);int a[4]={0},o=1;int len=strlen(s);for(int i=0;i<len;i++){if('0'<=s[i]&&s[i]<='9') a[o]=a[o]*10+s[i]-'0';else if(a[o]) o++; }n=a[1];m=a[2];return k=a[3]; } int read(int &o) {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=x*10+ch-'0';ch=getchar();}o=x*f; } void add_edge(int u,int v,int cap) {e[ent]=(edge){v,cap,head[u]};head[u]=ent++;e[ent]=(edge){u,0,head[v]};head[v]=ent++; } void make_new_edge(int day) {for(int i=3;i<=n+3-1;i++) add_edge(ld[i],++sz,INF),ld[i]=sz;for(int i=1;i<=m;i++){int t=day%cw[i][1],o=sps[i][t];if(o==ear) add_edge(ear,++sz,cw[i][0]),ls[i]=sz;else if(o==yue) add_edge(ls[i],yue,cw[i][0]),ls[i]=0;else {if(ls[i])add_edge(ls[i],ld[o],cw[i][0]);ls[i]=ld[o];}} } bool bfs(int s,int t) {memset(h,0,sizeof(h));int l=0,r=1;q[1]=s;h[s]=1;while(l<r){int u=q[++l];for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(h[v]||!e[i].cap) continue;h[v]=h[u]+1; q[++r]=v;}}return h[t]; } int dfs(int u,int res,int t) {if(u==t) return res;int flowout=0,f;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!e[i].cap||h[v]!=h[u]+1) continue;f=dfs(v,min(res,e[i].cap),t);e[i].cap-=f; e[i^1].cap+=f;flowout+=f; res-=f;if(!res) break;}if(!flowout) h[u]=-1;return flowout; } int Dinic(int s,int t) {while(bfs(s,t)){aim+=dfs(s,INF,t);}return aim; } void check_and_add(int a,int b,int c,int d) {c+=a; d+=b;if(c==0||c==n+1||d==0||d==m+1) return;int u=(a-1)*m+b,v=(c-1)*m+d;add_edge(u,v,INF); } int find(int x) {if(fa[x]!=x) return fa[x]=find(fa[x]);return x; } void unio(int x,int y) {int fx=find(x),fy=find(y);if(fx!=fy) fa[fy]=fx; } void _1908() {for(int i=1;i<=25;i++) fa[i]=i;for(int i=1;i<=m;i++){read(cw[i][0]);read(cw[i][1]);for(int j=0;j<cw[i][1];j++) {read(sps[i][j]);sps[i][j]+=2;if(j) for(int jj=0;jj<j;jj++)unio(sps[i][jj],sps[i][j]);}}if(find(yue)!=find(ear)) printf("0");else{int day=0;add_edge(3,ear,k); add_edge(yue,4,INF);for(int i=3;i<=n+3-1;i++) ld[i]=++sz;for(int i=1;i<=m;i++){int o=sps[i][0];if(o==ear) add_edge(ear,++sz,cw[i][0]),ls[i]=sz;else if(o!=yue) ls[i]=ld[o];}while(1){++day;make_new_edge(day);if(Dinic(3,4)==k) { printf("%d",day); break;}}} } void _1907() {int x,co=0;s=n*m+1;t=n*m+2;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){co=(i+j)%2;int u=(i-1)*m+j;scanf("%d",&x); tot+=x;if(!co){add_edge(s,u,x);check_and_add(i,j,-1,0);check_and_add(i,j,1,0);check_and_add(i,j,0,-1);check_and_add(i,j,0,1); } else add_edge(u,t,x);}printf("%d",tot-Dinic(s,t)); } int main() {if(special_read()) _1908();else _1907(); return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zj75211/p/6659240.html

總結(jié)

以上是生活随笔為你收集整理的线性规划与网络流24题●09方格取数问题13星际转移问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。