[UVALive 4865 Data Recovery] 疼疼最大流

【题目链接】http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=15554

【题目大意】

给定一个m*n的矩阵,矩阵里每个格子填一个[0,100]的数,有些格子被挖空了(用-1表示),让你向里面填数字。再给定每一行和每一列的和。

如果没有解,那么输出-1

有解的情况下,对于那些确定值的格子填出来,不能确定值的格子,用-1代替。

(m,n<=50)

样例1:

Input:

2 2

1 -1           //-1表示被挖空的不确定的位置

-1 -1

100 100      //每行的和都是100

100 100     //每列的和都是100

Output:

1 99

99 1

【算法分析】

首先用点分别代表行和列,然后形成二分图,行列之间的边就对应着格子。

然后加个源汇沙茶建边做一次最大流就可以得到(确定的格子不需要加边,直接对行列和减一下就可以了)。

无解什么的都解决了。

但是判定一个点是否必须填这个值就需要思考一下了。

由于一个流对应一个解,所以解不同对应着流不同。

我们看图中二分图中的红色的那条边:

假如它要减少流量,那么必须要在残余网络中存在类似这样的路径(注意箭头方向):

假如它要增加流量,那么必须要在残余网络中存在类似这样的路径(注意箭头方向):

实际上从残余网络上看,从二分图左边的点集指向右边点集的边可以视为是增加流量的边,从右边点集指向左边点集的边可以视为撤销原流的边。
于是乎,我们判定一条边上面的流值是否一定,只需要看这条边在残余网络中,是否存在一个点数>=3的环(=2的时候显然是没意义的,就是两个点之间跑),包含这条边就可以了。

实现随意,暴力可过。一开始写了个Floyd发现好难搞=2的环的情况,于是改回暴力dfs。

复杂度O(m^2*n^2)

【CODE】

#include #include #include #define clr(a) memset(a,0,sizeof(a))
const int N=55;
int m,n,S,T,Flow;
int map[N][N];
int c[N+N][N+N];
int v[N+N];
int v2[N+N];
int L[N+N];
int fa[N+N];
int Sx[N],Sy[N];

void init(){
     int i,j;
     clr(c);
     clr(Sx);
     clr(Sy);
     scanf("%d%d",&m,&n);
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++){
         scanf("%d",&map[i][j]);
         if (map[i][j]!=-1){
           Sx[i]-=map[i][j];
           Sy[j]-=map[i][j];
         }
         else c[i][j+m]=100;
       }
     for (i=1;i<=m;i++){int x; scanf("%d",&x); Sx[i]+=x;}
     for (i=1;i<=n;i++){int x; scanf("%d",&x); Sy[i]+=x;}
}

void build(){
     int i,j;
     S=m+n+1;
     T=m+n+2;
     for (i=1;i<=m;i++) c[S][i]=Sx[i];
     for (i=1;i<=n;i++) c[i+m][T]=Sy[i];
}

bool bfs(){
     int head=0,tail=1,i,j;
     for (i=1;i<=T;i++) v[i]=0;
     L[1]=S;
     v[S]=1;
     while (head!=tail){
           head++;
           for (i=1;i<=T;i++)
             if (c[L[head]][i]>0 && v[i]==0){
               v[i]=1;
               L[++tail]=i;
               fa[i]=L[head];
               if (i==T) return true;
             }
     }
     return false;
}

void change(){
     int nf=0x7FFFFFFF;
     for (int i=T;i!=S;i=fa[i])
       if (c[fa[i]][i]     for (int i=T;i!=S;i=fa[i]){
         c[fa[i]][i]-=nf;
         c[i][fa[i]]+=nf;
     }
     Flow+=nf;
}

void Edmonds_Karp(){
     Flow=0;
     while (bfs())
       change();
}

bool check(){
     int Sum=0;
     for (int i=1;i<=m;i++) Sum+=Sx[i];
     if (Sum!=Flow) return false;
     Sum=0;
     for (int i=1;i<=n;i++) Sum+=Sy[i];
     if (Sum!=Flow) return false;
     return true;
}

void dfs(int p){
     v[p]=1;
     int i;
     for (i=1;i<=m+n;i++){
         if (p==S && i==T || p==T && i==S) continue;
         if (c[p][i]>0 && !v[i]) dfs(i);
     }
}

void solve(){
     if (!check()){puts("-1"); return;}
     int i,j,k,l;
     for (i=1;i<=m;i++)
       for (j=m+1;j<=m+n;j++)if (map[i][j-m]==-1){
           S=i; T=j;
           for (k=1;k<=m+n;k++) v[k]=0;
           bool flag=false;
           if (c[i][j]>0){
             dfs(T);
             if (v[S]==1) flag=true;
           }
           if (!flag && c[j][i]>0){
             for (k=1;k<=m+n;k++) v[k]=0;
             dfs(S);
             if (v[T]==1) flag=true;
           }
           if (!flag) map[i][j-m]=c[j][i];
       }
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++){
           printf("%d",map[i][j]);
           if (j==n) putchar('n');
                else printf(" ");
       }
}

int main(){
    while (1){
          init();
          if (n+m==0) break;
          build();
          Edmonds_Karp();
          solve();
    }
    return 0;
}
【Others】

今天和AC、LCC做了一场比赛,我队累计切了10题,我显然属于打杂类型……水了4个题,难的都他们去搞了。

Mark一下这四道水题,以后出给小朋友还是可以的

C

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22045

代码:http://xiudaima.appspot.com/code/detail/4568015

状压dp,各种合并

D

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22046

代码:http://xiudaima.appspot.com/code/detail/4514015

模拟

K

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22053

代码:http://xiudaima.appspot.com/code/detail/4572008

DP,需要转一下思路

L

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22054

代码:http://xiudaima.appspot.com/code/detail/4442019

想出了n^2 per data的,直接交超时,于是打表交。因为表才1000,所以程序并不是很长,上面的代码是用来打表的。其实这个预处理可以放在程序前面,不过需要变一下,降为n^2。当时没怎么想到就直接n^3地打表了。

加入对话

8条评论

  1. 回复overture_wy:不是,他要每个格子都分别确定是否只能取一个值,我试过随机权值的费用流,但发现跑一遍费用流都超时= =(不排除我写搓)。如果上下界和单纯形应该都要枚举一条边然后看能不能调整他的权值吧?那样应该超时更严重。

留下评论

您的电子邮箱地址不会被公开。