Topcoder SRM570 900 CurvyonRails

题意：给定一个网格，一些格子是障碍不用管，剩余的格子是城市，你可以修建铁路，铁路的形状可以是直的或者弯的，也就是说可以以这个点为节点连接它四联通的其中两个方块。要求用一个或多个环来覆盖所有城市。对于有些关键点，如果这里是直轨道，会付出1的代价，如果不能覆盖，输出-1，否则输出最小代价。

这次该最小费用流了。x先考虑怎么判断有无解。很明显，既然是棋盘，想不染色不二分图都难。染成黑白后，对于黑点，S向其连2，黑点向周围的白点连1，白点向T连2，判断是否满流就好了。那么怎么计算代价呢？我们发现，如果要付出代价，那么一定是两个开口都给了同一列或者同一行，为了对此限制，我们拆点，分别管辖行和列。

如果这个点是黑关键点，我们向行对应的分身连一个容量1，费用0的边，再连一个容量1，费用1的边，表示如果只用一条边，不会产生费用，否则产生两条边的费用。列的话同理。

白关键点就不赘述了，其实也就是相较于反了一下。对于普通点，直接相对应的两个点分别连（2,0）就好了（因为没有限制），然后黑连向对应的白就好了。

跑费用流，不满流无解，满流输出费用即可。

 #include<bits/stdc++.h>

 using namespace std;

 #define INF 1e9

 #define N 5005

 #define id(i,j) ((i-1)*m+j)

 int n,m,TOT,S,T,P,head[N],d[N],a[N],p[N],cnt;

 bool vis[N];

 queue<int>q;

 char field[N][N];

 inline int read(){

     int x=,f=; char a=getchar();

     while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}

     while(a>='' && a<='') x=x*+a-'',a=getchar();

     return x*f;

 }

 struct edges{

     int fr,to,cap,flow,cost,next;

 }e[*N];

 inline void insert(int u,int v,int f,int c){

     e[cnt]=(edges){u,v,f,,c,head[u]};head[u]=cnt++;

     e[cnt]=(edges){v,u,,,-c,head[v]};head[v]=cnt++;

 }

 inline bool spfa(){

     memset(d,0x3f,sizeof(d));

     d[S]=; a[S]=INF; q.push(S);

     while(!q.empty()){

         int x=q.front(); q.pop(); vis[x]=;

         for(int i=head[x];i>=;i=e[i].next)

             if(d[e[i].to]>d[x]+e[i].cost && e[i].flow<e[i].cap){

                 d[e[i].to]=d[x]+e[i].cost; p[e[i].to]=i;

                 a[e[i].to]=min(a[x],e[i].cap-e[i].flow);

                 if(!vis[e[i].to]) vis[e[i].to]=,q.push(e[i].to);

             }

     }

     return d[T]<INF;

 }

 inline int mincf(){

     int u=T;

     while(u!=S){

         e[p[u]].flow+=a[T];

         e[p[u]^].flow-=a[T];

         u=e[p[u]].fr;

     }

     TOT-=a[T];

     return a[T]*d[T];

 }

 int main(){

     n=read(); m=read();

     for(int i=;i<=n;i++)

     scanf("%s",field[i]+);

     S=; T=*n*m+; P=n*m; TOT=;

     memset(head,-,sizeof(head));

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++){

                if(field[i][j]=='w') continue;

             if((i+j)%==){

                 insert(S,id(i,j),,); TOT+=;

                 if(field[i][j]!='C') insert(id(i,j),id(i,j)+*P,,),insert(id(i,j),id(i,j)+P,,);

                 else {

                     insert(id(i,j),id(i,j)+P,,); insert(id(i,j),id(i,j)+P,,);

                     insert(id(i,j),id(i,j)+*P,,); insert(id(i,j),id(i,j)+*P,,);

                 }

                 if(j-> && field[i][j-]!='w') insert(id(i,j)+P,id(i,j-)+P,,);

                 if(j+<=m && field[i][j+]!='w' ) insert(id(i,j)+P,id(i,j+)+P,,);

                 if(i-> && field[i-][j]!='w') insert(id(i,j)+*P,id(i-,j)+*P,,);

                 if(i+<=n && field[i+][j]!='w') insert(id(i,j)+*P,id(i+,j)+*P,,);

             }else{

                 insert(id(i,j),T,,);

                 if(field[i][j]!='C') insert(id(i,j)+*P,id(i,j),,),insert(id(i,j)+P,id(i,j),,);

                 else{

                     insert(id(i,j)+P,id(i,j),,); insert(id(i,j)+P,id(i,j),,);

                     insert(id(i,j)+*P,id(i,j),,); insert(id(i,j)+*P,id(i,j),,);

                 }

             }

         }

     int ans=;

     while(spfa()) ans+=mincf();

     if(TOT) ans=-;

     printf("%d\n",ans);

 }

巴特西

Topcoder SRM570 900 CurvyonRails

最新文章

热门文章