題意：給定一個網格，一些格子是障礙不用管，剩余的格子是城市，你可以修建鐵路，鐵路的形狀可以是直的或者彎的，也就是說可以以這個點為節點連接它四聯通的其中兩個方塊。要求用一個或多個環來覆蓋所有城市。對于有些關鍵點，如果這里是直軌道，會付出1的代價，如果不能覆蓋，輸出-1，否則輸出最小代價。

這次該最小費用流了。x先考慮怎么判斷有無解。很明顯，既然是棋盤，想不染色不二分圖都難。染成黑白后，對于黑點，S向其連2，黑點向周圍的白點連1，白點向T連2，判斷是否滿流就好了。那么怎么計算代價呢？我們發現，如果要付出代價，那么一定是兩個開口都給了同一列或者同一行，為了對此限制，我們拆點，分別管轄行和列。

如果這個點是黑關鍵點，我們向行對應的分身連一個容量1，費用0的邊，再連一個容量1，費用1的邊，表示如果只用一條邊，不會產生費用，否則產生兩條邊的費用。列的話同理。

白關鍵點就不贅述了，其實也就是相較于反了一下。對于普通點，直接相對應的兩個點分別連（2,0）就好了（因為沒有限制），然后黑連向對應的白就好了。

跑費用流，不滿流無解，滿流輸出費用即可。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define INF 1e9 4 #define N 5005 5 #define id(i,j) ((i-1)*m+j) 6 int n,m,TOT,S,T,P,head[N],d[N],a[N],p[N],cnt; 7 bool vis[N]; 8 queue<int>q; 9 char field[N][N]; 10 inline int read(){ 11 int x=0,f=1; char a=getchar(); 12 while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();} 13 while(a>='0' && a<='9') x=x*10+a-'0',a=getchar(); 14 return x*f; 15 } 16 struct edges{ 17 int fr,to,cap,flow,cost,next; 18 }e[2*N]; 19 20 inline void insert(int u,int v,int f,int c){ 21 e[cnt]=(edges){u,v,f,0,c,head[u]};head[u]=cnt++; 22 e[cnt]=(edges){v,u,0,0,-c,head[v]};head[v]=cnt++; 23 } 24 inline bool spfa(){ 25 memset(d,0x3f,sizeof(d)); 26 d[S]=0; a[S]=INF; q.push(S); 27 while(!q.empty()){ 28 int x=q.front(); q.pop(); vis[x]=0; 29 for(int i=head[x];i>=0;i=e[i].next) 30 if(d[e[i].to]>d[x]+e[i].cost && e[i].flow<e[i].cap){ 31 d[e[i].to]=d[x]+e[i].cost; p[e[i].to]=i; 32 a[e[i].to]=min(a[x],e[i].cap-e[i].flow); 33 if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to); 34 } 35 } 36 return d[T]<INF; 37 } 38 inline int mincf(){ 39 int u=T; 40 while(u!=S){ 41 e[p[u]].flow+=a[T]; 42 e[p[u]^1].flow-=a[T]; 43 u=e[p[u]].fr; 44 } 45 TOT-=a[T]; 46 return a[T]*d[T]; 47 } 48 49 int main(){ 50 n=read(); m=read(); 51 for(int i=1;i<=n;i++) 52 scanf("%s",field[i]+1); 53 S=0; T=3*n*m+1; P=n*m; TOT=0; 54 memset(head,-1,sizeof(head)); 55 for(int i=1;i<=n;i++) 56 for(int j=1;j<=m;j++){ 57 if(field[i][j]=='w') continue; 58 if((i+j)%2==0){ 59 insert(S,id(i,j),2,0); TOT+=2; 60 if(field[i][j]!='C') insert(id(i,j),id(i,j)+2*P,2,0),insert(id(i,j),id(i,j)+P,2,0); 61 else { 62 insert(id(i,j),id(i,j)+P,1,1); insert(id(i,j),id(i,j)+P,1,0); 63 insert(id(i,j),id(i,j)+2*P,1,1); insert(id(i,j),id(i,j)+2*P,1,0); 64 } 65 if(j-1>0 && field[i][j-1]!='w') insert(id(i,j)+P,id(i,j-1)+P,1,0); 66 if(j+1<=m && field[i][j+1]!='w' ) insert(id(i,j)+P,id(i,j+1)+P,1,0); 67 if(i-1>0 && field[i-1][j]!='w') insert(id(i,j)+2*P,id(i-1,j)+2*P,1,0); 68 if(i+1<=n && field[i+1][j]!='w') insert(id(i,j)+2*P,id(i+1,j)+2*P,1,0); 69 }else{ 70 insert(id(i,j),T,2,0); 71 if(field[i][j]!='C') insert(id(i,j)+2*P,id(i,j),2,0),insert(id(i,j)+P,id(i,j),2,0); 72 else{ 73 insert(id(i,j)+P,id(i,j),1,1); insert(id(i,j)+P,id(i,j),1,0); 74 insert(id(i,j)+2*P,id(i,j),1,1); insert(id(i,j)+2*P,id(i,j),1,0); 75 } 76 } 77 } 78 int ans=0; 79 while(spfa()) ans+=mincf(); 80 if(TOT) ans=-1; 81 printf("%d\n",ans); 82 }

?

轉載于:https://www.cnblogs.com/enigma-aw/p/6237246.html

總結

以上是生活随笔為你收集整理的Topcoder SRM570 900 CurvyonRails的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。