## UVALive 6141

### Binary Matrix 2

/* ***
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

#include

#include

#include

#include

#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 cur[MAXN];
int dis[MAXN];
bool vis[MAXN];
int ss,tt,N;//源点、汇点和点的总个数（编号是0~N-1）,不需要额外赋值，调用会直接赋值
int min_cost, max_flow;
void init()
{
tot = 0;
}
void addedge(int u,int v,int cap,int cost)
{
}
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(x
n%m != 0)continue;
int c = xn/m;
if(abs(sum-n
x) >= 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++)
{
}
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;
}

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 304.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%