UVALive 6141 Binary Matrix 2 （ZKW费用流）

UVALive 6141

Binary Matrix 2

用最小费用最大流做。题目链接： UVALive VJ 题意就是n*m的01矩阵。可以把0翻转为1,1翻转为0，求最少的翻转次数，使得每行1的个数相同，每列1的个数相同。构建一个费用流模型。首先可以枚举最终状态，假如最终每行有i个1，那么每列1的个数就是i*n/m (当然要保证整除) 左边是n个点，右边是m个点。源点到左边n个点的费用就是0，流量就是i. 右边的m个点到汇点的边费用是0，流量是i*n/m 然后左边到右边的点，两两之间的边就是流量为1的，费用的话看对应的位置是0还是1，是1的话，费用是-1，是0的话费用是1. 那么这次需要的最少翻转次数就是最小费用+原来1的总个数。建图的理解可以这样想，首先费用是原来1的总个数。就相当于把所有1都翻转为0，然后建图以后，如果走一条原来就是1的边，那么加费用为-1的边，表示如果利用一个的话，费用就是-1了。相反如果走原来为0的边，那么费用要+1. 这样最小费用 + sum 就是答案了。这种类似二分图的费用流，路径短，边很多。使用SPFA的费用流是很慢的，对于这题SPFA的费用流就T了。写这题的目的就是为了写一个重口味费用流的模板。 zkw费用流适合这种二分图类型的图。

/* ***
Author :kuangbin
Created Time :2014/8/2 10:21:53
File Name :E:\2014ACM\区域赛练习\2012\2012Hatyai\A.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

const int MAXN = 100;
const int MAXM = 20000;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow,cost;
Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,int _cost = 0):
to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost){}
}edge[MAXM];

struct ZKW_MinCostMaxFlow
{
int head[MAXN],tot;
int cur[MAXN];
int dis[MAXN];
bool vis[MAXN];
int ss,tt,N;//源点、汇点和点的总个数（编号是0~N-1）,不需要额外赋值，调用会直接赋值
int min_cost, max_flow;
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tot] = Edge(v,head[u],cap,0,cost);
head[u] = tot++;
edge[tot] = Edge(u,head[v],0,0,-cost);
head[v] = tot++;
}
int aug(int u,int flow)
{
if(u == tt)return flow;
vis[u] = true;
for(int i = cur[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] == dis[v] + edge[i].cost)
{
int tmp = aug(v,min(flow,edge[i].cap-edge[i].flow));
edge[i].flow += tmp;
edge[i^1].flow -= tmp;
cur[u] = i;
if(tmp)return tmp;
}
}
return 0;
}
bool modify_label()
{
int d = INF;
for(int u = 0;u < N;u++)
if(vis[u])
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap>edge[i].flow && !vis[v])
d = min(d,dis[v]+edge[i].cost-dis[u]);
}
if(d == INF)return false;
for(int i = 0;i < N;i++)
if(vis[i])
{
vis[i] = false;
dis[i] += d;

        }
    return true;
}
/\*
 \* 直接调用获取最小费用和最大流
 \* 输入: start-源点，end-汇点，n-点的总个数（编号从0开始）
 \* 返回值: pair<int,int> 第一个是最小费用，第二个是最大流
 */
pair<int,int> mincostmaxflow(int start,int end,int n)
{
    ss = start, tt = end, N = n;
    min\_cost = max\_flow = 0;
    for(int i = 0;i < n;i++)dis\[i\] = 0;
    while(1)
    {
        for(int i = 0;i < n;i++)cur\[i\] = head\[i\];
        while(1)
        {
            for(int i = 0;i < n;i++)vis\[i\] = false;
            int tmp = aug(ss,INF);
            if(tmp == 0)break;
            max_flow += tmp;
            min_cost += tmp*dis\[ss\];
        }
        if(!modify_label())break;
    }
    return make\_pair(min\_cost,max_flow);
}

}solve;
char str[110][110];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n,m;
scanf(“%d”,&T);
int iCase = 0;
while(T–)
{
iCase++;
scanf(“%d%d”,&n,&m);
int sum = 0;
for(int i = 0;i < n;i++)
{
scanf(“%s”,str[i]);
for(int j = 0;j < m;j++)
if(str[i][j] == ‘1’)
sum++;
}
int ans = min(sum,nm-sum);
for(int x = 1;x < m;x++)
{
if(xn%m != 0)continue;
int c = xn/m;
if(abs(sum-nx) >= ans)continue;
solve.init();
for(int i = 0;i < n;i++)solve.addedge(n+m,i,x,0);
for(int j = 0;j < m;j++)solve.addedge(j+n,n+m+1,c,0);
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
{
if(str[i][j] == ‘1’)solve.addedge(i,j+n,1,-1);
else solve.addedge(i,j+n,1,1);
}
pair<int,int> tmp = solve.mincostmaxflow(n+m,n+m+1,n+m+2);
ans = min(ans,tmp.first+sum);
}
printf(“Case %d: %d\n”,iCase,ans);
}
return 0;
}