[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地打表了。