编程之美2014年资格赛第三题——格格取数(已过大数据)

By | 03月11日
Advertisement

题目3 :格格取数

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

给你一个m x n (1 <=m, n <= 100)的矩阵A (0<=aij<=10000),要求在矩阵中选择一些数,要求每一行,每一列都至少选到了一个数,使得选出的数的和尽量的小。

输入

多组测试数据。首先是数据组数T

对于每组测试数据,第1行是两个正整数m, n,分别表示矩阵的行数和列数。

接下来的m行,每行n个整数,之间用一个空格分隔,表示矩阵A的元素。

输出

每组数据输出一行,表示选出的数的和的最小值。

数据范围

小数据:1 <= m, n<= 5

大数据:1 <= m, n<= 100

样例输入

2

3 3

1 2 3

3 1 2

2 3 1

5 5

1 2 3 4 5

5 1 2 3 4

4 5 1 2 3

3 4 5 1 2

2 3 4 5 1

样例输出

Case 1: 3

Case 2: 5

题目要求使得每一行、每一列都至少有一个数被取出,并使得取出的和最小。开始就觉得是每行、每列都去一个这样是最小的。网上流传很广的一组样例:

4 4

1 1 100

100 100 1

100 100 1

能够很轻松的否定掉这个思路。开始按照这个思路写的最小费用最大流,是因为最大流为max(n,m)。但是,显然不是这个样子的。真正的流量是不能够确定的。所以,直接用最小费用最大流就不行了。

那么,这里我们可以进行一些处理。让没有必要的流量直接从源点流向汇点。这样一来,总流量就一定是n*m了。而对于要通过行点和列点的流量是多少呢?经过分析可以发现。如果第i行和第j列都已经取出了一个数(不是a[i][j]时),那么a[i][j]必然是不会被取出的。

现在要解决的问题就是如何保证行点和列点至少流过一次,且不会存在两个已经流过的点在被同时流一次。将行点和列点进行拆分。共2*m个行点和2*n个列点。那么就是源点到m个行点的流量为1,费用为负无穷,n个列点到汇点的流量为1,费用为负无穷。剩下的m个行点的流量为n,费用为0,n个列点的流量为m,费用为0.源点到汇点的流量为n*m,费用为0.同时,我们需要建立一个超级源点,保证总流量一定是n*m。即超级源点到源点的流量是n*m。这样就能保证得到的费用是最小值了,最后的结果就是得到的费用加上(n+m)*负无穷。

可以看出来,如果某个行点和某个列点已经被选择,那么如果存在一个流流过这两个点,那么代价必然是a[i][j],显然不如直接从源点流向汇点。所以,就避免出现第i行和第j列都已经取出了一个数且不是a[i][j]时,取出了a[i][j]这种多余情况。同时,可以得到,负无穷只要能使最大边权+负无穷小于0即可。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <cstring> #define INF 99999999 #define MAXN 20000 using namespace std; const int M = 100010;//边 const int N = 500;  struct Node//边,点f到点t,流量为c,费用为w {     int st, ed;     int flow, cost;     int next; }edge[M];  int head[N], dis[N], q[N], pre[N], cnt;//cnt为已添加的边数,head为邻接表,dis为花费,pre为父亲节点 bool vis[M]; int n, m, s ,t; int graph[110][110];  void init() {  memset(head, -1, sizeof(head));     cnt = 0; }  void add_edge(int f, int t, int d1, int d2, int w) {//f到t的一条边,流量为d1,反向流量d2,花费w,反向边花费-w(可以反悔)    edge[cnt].st = f;   edge[cnt].ed = t;   edge[cnt].flow = d1;    edge[cnt].cost = w;     edge[cnt].next = head[f];   head[f] = cnt++;    edge[cnt].st = t;   edge[cnt].ed = f;   edge[cnt].flow = d2;    edge[cnt].cost = -w;    edge[cnt].next = head[t];   head[t] = cnt++; }  bool spfa(int s, int t, int n) {    int i, tmp, l, r;   memset(pre, -1, sizeof(pre));   for(i = 0; i < n; ++i)     {         dis[i] = INF;     }     dis[s] = 0;     q[0] = s;   l = 0, r = 1;   vis[s] = true;  while(l != r)     {         tmp = q[l];         l = (l + 1) % (n + 1);      vis[tmp] = false;       for(i = head[tmp]; i!=-1; i = edge[i].next)         {           if(edge[i].flow && dis[edge[i].ed] > dis[tmp] + edge[i].cost)            {               dis[edge[i].ed] = dis[tmp] + edge[i].cost;              pre[edge[i].ed] = i;                if(!vis[edge[i].ed])                {                   vis[edge[i].ed] = true;                     q[r] = edge[i].ed;                  r = (r + 1) % (n + 1);              }           }       }   }   if(pre[t] == -1)    {       return false;   }   return true; }  void MCMF(int s, int t, int n, int &flow, int &cost) {//起点s,终点t,点数n,最大流flow,最小花费cost    int tmp, arg;   flow = cost = 0;    while(spfa(s, t, n))     {      arg = INF;      tmp = t;        while(tmp != s)         {           arg = min(arg, edge[pre[tmp]].flow);            tmp = edge[pre[tmp]].st;        }       tmp = t;        while(tmp != s)         {           edge[pre[tmp]].flow -= arg;             edge[pre[tmp] ^ 1].flow += arg;             tmp = edge[pre[tmp]].st;        }       flow += arg;        cost += arg * dis[t];   } }  int main() {   int x;  scanf("%d",&x);     for(int r = 1;r <= x;r++)    {       init();         scanf("%d%d",&m,&n);        for(int i = 1;i <= m;i++)        {           for(int j = 1;j <= n;j++)            {               scanf("%d",&graph[i][j]);               add_edge(i,2*m+j,1,0,graph[i][j]);              add_edge(i,2*m+n+j,1,0,graph[i][j]);                add_edge(i+m,2*m+n+j,1,0,graph[i][j]);              add_edge(i+m,2*m+j,1,0,graph[i][j]);            }       }       for(int i = 1;i <= m;i++)        {           add_edge(0,i,1,0,-MAXN);            add_edge(0,i+m,n,0,0);      }       t = 2 * m + 2 * n + 1;      for(int i = 1;i <= n;i++)        {           add_edge(i+2*m,t,1,0,-MAXN);            add_edge(2*m+n+i,t,m,0,0);      }       s = t + 1;      add_edge(s,0,n*m,0,0);      add_edge(0,t,n*m,0,0);      int flow ,cost;         MCMF(s,t,t+2,flow,cost);        printf("Case %d: %dn",r,cost+(m+n)*MAXN);   }   return 0; }

Similar Posts:

  • 微软2编程之美2015资格赛

    证明过程参考编程之美2015资格赛题解 题目1 :2月19日 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给定两个日期,计算这两个日期之间有多少个2月29日(包括起始日期). 只有闰年有2月29日,满足以下一个条件的年份为闰年: 1. 年份能被4整除但不能被100整除 2. 年份能被400整除 输入 第一行为一个整数T,表示数据组数. 之后每组数据包含两行.每一行格式为"month day, year",表示一个日期.month为{"Janua

  • 编程之美,JAVA控制CPU的使用率(2),完美曲线

    中午抽个时间,把代码完成了,从效果看,不算很完美,不过我已经很满足了. /** * 编程之美,JAVA控制CPU的使用率(2),完美曲线 * * @author 赵学庆,Java世纪网(java2000.net) * */ public class T { public static void main(String[] args) throws Exception { // 角度的分割 final double SPLIT = 0.01; // // 2PI分割的次数,也就是2/0.01个,正

  • 编程之美:小飞的电梯调度

    解法1枚举:省略 解法2cost:i+1层: Y+N1+N2-N3 i层: Y i-1层 : Y-N1+N2+N3 可知cost(i-1)>cost(i)的条件:N1<N2+N3,两边同时加N2得到,N1+N2<N2*2+N3 (1) cost(i+1)<cost(i)的条件:N1+N2<N3(2) cost(i+1) <cost(i-1)的条件:N1<N3即N1+N2<N2+N3(3) 初始条件下:N1=0,N2<N3,(1)(2)(3)都满足,co

  • 编程之美2.17——数组循环移位——解法…

    //---------------------------------------------- // Author :心海 // Date :2013-12-02 // Blog :http://blog.sina.com.cn/u/2116533530 // Copyright :anyone // PS :欢迎拍砖.指正.一起学习,共同进步. //----------------------------------------------- #include<stdio.h> void

  • 编程之美3.7队列中取最大值操作

    /* 编程之美3.7队列中取最大值操作 采用STL中的已有stack 方法:用的文中的方法3:保存栈中最大值可以简单实现 */ #include<stack> #include<iostream> using namespace std; template<typename T> class Queue { public: void push(T data) { stackIn.push(data); if(stackInCopy.empty()) stackInCop

  • 编程之美2014---大神与三位小伙伴

    问题 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 L国是一个有着优美景色且物产丰富的国家,很多人都喜欢来这里旅游并且喜欢带走一些纪念品,大神同学也不例外.距离开L国的时间越来越近了,大神同学正在烦恼给她可爱的小伙伴们带什么纪念品好,现在摆在大神同学面前的有三类纪念品A, B, C可以选择,每类纪念品各有N种.其中种类为A_i, B_i, C_i的纪念品价值均为i, 且分别有N+1-i个剩余.现在大神同学希望在三类纪念品中各挑选一件然后赠送给她的三名可爱的小伙伴,但

  • 编程之美2014-资格赛-题目2:大神与三位小伙伴

    时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 L国是一个有着优美景色且物产丰富的国家,很多人都喜欢来这里旅游并且喜欢带走一些纪念品,大神同学也不例外.距离开L国的时间越来越近了,大神同学正在烦恼给她可爱的小伙伴们带什么纪念品好,现在摆在大神同学面前的有三类纪念品A, B, C可以选择,每类纪念品各有N种.其中种类为A_i, B_i, C_i的纪念品价值均为i, 且分别有N+1-i个剩余.现在大神同学希望在三类纪念品中各挑选一件然后赠送给她的三名可爱的小伙伴,但是她又

  • 【简单数学&amp;amp;DP】闰年计数&amp;amp;回文串计数 _Hihocoder战场 @ 编程之美2015资格赛

    题目1 : 2月29日 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给定两个日期,计算这两个日期之间有多少个2月29日(包括起始日期). 只有闰年有2月29日,满足以下一个条件的年份为闰年: 1. 年份能被4整除但不能被100整除 2. 年份能被400整除 输入 第一行为一个整数T,表示数据组数. 之后每组数据包含两行.每一行格式为"month day, year",表示一个日期.month为{"January", "Feb

  • 编程之美8:链表常见面试笔试题集合

    楼楼这篇文章决定把面试中关于链表的常见面试题或者笔试题整理一下,现在目前为止只整理了四个题目,后面如果楼主看到还有什么题目需要记录的话,会一直更新的.楼楼略菜,如果有什么错误或不对的地方,希望各位看官留言指出,谢谢啦! 今天又是福来day了,好伤心啊,一周又过去了. 第一题:单链表是否存在环?环的入口是什么? 解法:设置两个快慢指针fast和slow指针,fast指针一下走两步,slow指针一下走一步,若最终fast == slow,那么就证明单链表中一定会有环.如果没有环的话,fast比slo

  • 编程之美2013-传话游戏

    时间限制: 1000ms 内存限制: 256MB 描述 Alice和Bob还有其他几位好朋友在一起玩传话游戏.这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位.然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位……以此类推,直到倒数第二位告诉Bob.两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释.最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家. 由于传话过程中可能出现

Tags: