朝气蓬勃.理论希图       " />
当前位置:必发365电子游戏 > 编程 > 帕Terry克在编制程序比赛
帕Terry克在编制程序比赛
2019-12-19

[Wf2017]Mission Improbable

必发365电子游戏,Time Limit: 1 Sec  Memory Limit: 1024 MB
Submit: 105  Solved: 49
[Submit][Status][Discuss]

style="font-family: 华文草书; font-size: x-large;">朝气蓬勃.理论希图

        那二日看见了图论的二部图,闲着没事就水了意气风发道。

        先看增广路的概念: style="font-family: 华文宋体; font-size: x-large;">增广路,也称增广轨或交错轨:
若P是图G中一条连通五个未相称极点的渠道,况且归于M的边和不归属M的边(即已相称和待相配的边卡塔尔(英语:State of Qatar)在P上轮番现身,则称P为绝对于M的一条增广路线。

        由增广路的概念能够生产下述五个结论:

  1. P的门路长度必定为奇数,第一条边和尾声一条边都不归于M。
  2. 不断追寻增广路能够收获二个越来越大的相配M’,直到找不到更加多的增广路,M为G的最大相配当且仅当官样文章M的增广路线。
  3. 最大相称数M+最大独立数N=总的结点数,增广路首要采纳于匈牙利(Magyarország卡塔尔国算法中,用于求二分图最大相配。    

    style="font-family: 华文燕书; font-size: x-large;">        无向图G为二分图的放量须求条件是,G至罕有极度相反,且其具备回路的长短均为偶数。

        二分图相称可用匈牙利(Magyarország卡塔尔(قطر‎算法,离散中学过,正是找一条轮换链,让路径的起源和终极皆以还从未匹配过的点,路线经过的连线是黄金年代 style="font-family: 华文楷书; font-size: x-large;">条没被相配、一条已经十分过,再下一条又没相配那样轮流地涌出,鲜明路线里没被相称的连线比已经十分了的连线多一条,于是 style="font-family: 华文燕书; font-size: x-large;">改进相配图,把门路里存有相配过的连线去掉匹配关系,把还未相称的连线产生相称的,那样相配数就比原先多1个。不断实施上述 style="font-family: 华文草书; font-size: x-large;">操作,直到找不到那般的不二诀要结束。

style="font-family: 华文小篆; font-size: x-large;">二.算法完成

        以POJ1274为例直接去AC吧。

import java.util.Arrays;

import java.util.Scanner;

public class POJ1274 {

  /*

   * 题意: n牛,m个房子,每个牛都只住在自己想住的房子里面,

   * 一个房子只能住一个牛,问最多可以安排多少头牛入住

   */

  static boolean map[][];

  static boolean vis[];

  //记录匹配点号

  static int path[];

  static int m,n;

  

  public static void main(String[] args) {

    

    Scanner sc = new Scanner(System.in);

    while(sc.hasNext()) {

      n = sc.nextInt();//n牛

      m = sc.nextInt();//m屋

      map = new boolean[n][m];

      int num;

      for(int i=0; i<n; i++) {

        num = sc.nextInt();

        for(int j=0; j<num; j++) {

          int k = sc.nextInt();

          map[i][k-1] = true;

        }

      }

      int cnt = 0;

      /*

       * 表示牛棚和哪个牛配对

       */

      path = new int[m];

      /*

       * 由于牛编号从0开始,所以不能初始化为0

       * wa了几次

       */

      Arrays.fill(path,-1);

      vis = new boolean[m];

      for(int i=0; i<n; i++) {

        Arrays.fill(vis,false);

        if(find(i)) {

          cnt++;

        }

      }

      System.out.println(cnt);

    }

    sc.close();

  }

  private static boolean find(int s) {

    

    for(int i=0; i<m; i++) {

      

      if(map[s][i] && vis[i]==false) {

        vis[i] = true;

        /*

         * /如果i未在前一个匹配M中 || i在匹配M中,但是从与i相邻的节点出发可以有增广路   

         */

        if(path[i]==-1 || find(path[i])) {

          path[i] = s;

          return true;

        }

      }

    }

    return false;

  }

}

Description

那是青春里三个天候晴朗的吉日,你筹划去看看你的故交Patrick,也是您后边的作案同伴。Patrick在编制程序竞技

上豪赌输掉了一大笔钱,所以她必要再干生龙活虎票。为此他索要您的帮带,固然你早就洗肠涤胃了。你刚初阶十分不情愿,

因为您或多或少也不想再重临那条老路上了,可是你以为听一下他的安插也何足道哉。在隔壁的一个库房里有一堆物品,

含有部分弥足爱慕的开销性构件,Patrick盘算从当中尽恐怕多地偷些东西出来。那意味要找一条进去的路,弄晕安全保卫人

员,穿过形形色色的激光射线,你懂的,都是广大的劫掠技术。然则,货仓的中坚道具了风华正茂套Patrick搞不定的安全保卫系

统。那也是他须求你扶植她之处。那批货品被放置在有个别宏伟的立方体箱里,每种箱子的尺码没什么差异的。那些

箱子聚积成多数齐整的堆,种种箱子能够象征成三个三个维度的网格。安保系统每一种小时会用三台相机对那堆货品实行

壹次拍录,相机分别为:前置相机(front camera卡塔尔(قطر‎,侧置相机(side camera卡塔尔国和顶置相机(top camera卡塔尔(قطر‎。前置相机的照

片显得了每豆蔻年华行最高的这堆箱子的惊人,侧置相机突显了每一列最高的那堆箱子的可观,顶置相机展现了各样地方是

否存在一群箱子。倘诺安全保卫系统开采此外一张相片并发了转移,它会立时拉响警报。少年老成旦 Patrick 进去了,他会确

定每堆箱子的惊人并且发给你。图1显示了后生可畏种网格或者的停放,以至每台相机会获取的视图。

图 1. 网格的中度值与相应的卡片机视图。

图 2. 洗劫后网格大概的中度值。

 

Patrick想尽量多偷走一些箱子。由于他无法弄坏安全保卫种类,他盘算重新安顿剩余每堆箱子的停放,使得下一次相

机取像时会拿到平等的照片,进而骗过安全保卫类别。在上头的例子中,他能够偷走七个箱子。图2显示了后生可畏种可能的剩

余箱子的摆设方案能使得安全保卫系统感到与原安放意况如出一辙。Patrick想请您帮他明确在承保能骗过安全保卫系统的事态

下他最多能偷走多少个箱子。你会帮她干完那最终大器晚成票么?

Input

首先行包涵多少个整数r(1≤r≤100卡塔尔国和c(1≤n≤100卡塔尔(قطر‎,分别代表网格的行数与列数。

接下去r行,每行包罗c个整数,表示对应行上每堆立方体箱的惊人(箱子的多寡)。

有着的莫斯中国科学技术大学学在0到10^9之间 (含边界卡塔尔国 。

Output

输出在不被发觉的景观下最多能偷走多少箱子。

Sample Input

样例1
5 5
1 4 0 5 2
2 1 2 0 1
0 2 3 4 4
0 3 0 3 1
1 2 2 1 1
样例2
2 3
50 20 3
20 10 3

Sample Output

样例1
9
样例2
30

帕Terry克在编制程序比赛。 

题解:

那道题应该什么去想,左边包车型客车,后面包车型地铁相机,就是行和列的最大值,而地点的双反相机,只会是推断该点有无,

行的最大值有望是列的最大值,那么就可以偷更加多的箱子,所以只要该点是行列的最大值,就连一条边,

然后就ok了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define MAXN 100000+10 
 7 using namespace std;
 8 typedef long long LL; 
 9 struct ed{LL v,next;}edge[MAXN]; 
10 LL match[220],head[220],vis[220],n,m; 
11 LL map[220][220],sum=0,mh[220],ml[220]; 
12 void add(LL u,LL v){ 
13     static LL tot=0; 
14     edge[++tot].v=v; 
15     edge[tot].next=head[u]; 
16     head[u]=tot; 
17 } 
18 bool dfs(LL u){ 
19     for(LL i=head[u];i;i=edge[i].next){ 
20         LL v=edge[i].v; 
21         if(vis[v])continue; 
22         vis[v]=1; 
23         if(!match[v]||dfs(match[v])){ 
24             match[v]=u; 
25             return true; 
26         } 
27     } 
28     return false; 
29 } 
30 int main(){ 
31     scanf("%lld%lld",&n,&m); 
32     for(LL i=1;i<=n;i++) 
33         for(LL j=1;j<=m;j++){ 
34             scanf("%lld",&map[i][j]); 
35             mh[i]=max(mh[i],map[i][j]); 
36             ml[j]=max(ml[j],map[i][j]); 
37             if(map[i][j])sum+=map[i][j]-1; 
38         } 
39     for(LL i=1;i<=n;i++) 
40         for(LL j=1;j<=m;j++) 
41             if(mh[i]&&map[i][j]&&mh[i]==ml[j])add(i,n+j); 
42     for(LL i=1;i<=n;i++)if(mh[i])sum-=mh[i]-1; 
43     for(LL i=1;i<=m;i++)if(ml[i])sum-=ml[i]-1; 
44     for(LL i=1;i<=n;i++){ 
45         memset(vis,0,sizeof(vis)); 
46         if(mh[i]&&dfs(i))sum+=mh[i]-1; 
47     } 
48     printf("%lld",sum); 
49     return 0; 
50 }