【题目链接】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地打表了。
，顿时觉得有点假。。。
，然后+个eps以后就Y了。
，然后就切掉了~Orz！！！！
