多重匹配

POJ 2289 Jamie’s Contact Groups

Posted on

最近网络流有点写累了,就尝试着写了一下二分图。
这是我第一道二分图多重匹配的题目,基本上是看着模板敲的……
因为中间在main函数内外都定义了n,m ,搞得我debug了好久……

二分图多重匹配想比喻二分图单匹配来说,只是多加了几步,本质上还是一样的。基本上看代码就能看懂。

题意:
有个女神的备胎很多,每次找备胎都很麻烦,搞得她很困扰。现在女神想把他的备胎们分成m组,根据关系有的必须放在特别的组,但是女神数学不好,于是女神随手找了个备胎帮助计算,在满足条件的情况下有个组内人数max,现在要你求最小的max。

思路:
二分人数+多重匹配。
最大流也可。二分到汇点的容量即可。

这里有个小麻烦,就是有不定数量的数字。
一般人会立马想到,最麻烦的getchar() , 好一点的想到 stringstream
这里比较合适的应该是 一起输入一个数字和字符,如果字符是换行符号则退出。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int n, m, maxcap;
bool vis[maxn], g[maxn][maxn];
int link[maxn][maxn], vlink[maxn];
char buf[60];

bool dfs(int u)
{
    each(i, m) if (g[u][i] && !vis[i])
    {
        vis[i] = true;
        if (vlink[i] < maxcap) {
            link[i][vlink[i]++] = u;
            return true;
        }
        each(j, vlink[i]) if (dfs(link[i][j]))
        {
            link[i][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary(int mid)
{
    maxcap = mid;
    fill(vlink, 0);
    each(i, n)
    {
        fill(vis, false);
        if (!dfs(i))
            return false;
    }
    return true;
}

inline void input(int u)
{
    int a;
    char c;
    scanf("%s", buf);
    while (true) {
        scanf("%d%c", &a, &c);
        g[u][a] = true;
        if (c == '\n')
            break;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while (scanf("%d %d", &n, &m) != EOF && (n || m)) {
        fill(g, false);
        each(i, n) input(i);
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (hungary(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}
构造

Codeforces 388 B Fox and Minimal path

Posted on

难得写的构造题,比赛的时候没写出来,听薛昊说的时候就理解了。
这种构图方法还是欠缺……

题意:
起点 1,终点 2,构造一个图,使得最短路数量为 k 。

思路:
这种题一般都是二进制分解做,关键就是构造出二进制的图,然后控制路径长度相同即可。这里提供一种构造方法。

点数最多 1e9 每行30个节点足够

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

//#define DEBUG

using namespace std;

const int maxn = 110;
const int inf = 0x3f3f3f3f;
int k;
char mat[maxn][maxn];

int main()
{
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++)
            mat[i][j] = 'N';
    mat[2][11] = mat[11][2] = mat[1][41] = mat[41][1] = mat[1][71] = mat[71][1] = 'Y';
    for (int i = 11; i < 40; i++)
        mat[i][i + 1] = mat[i + 1][i] = 'Y';
    for (int i = 41; i < 70; i++) {
        mat[i][i + 1] = mat[i + 1][i] = 'Y';
        mat[i][i + 30 + 1] = mat[i + 30 + 1][i] = 'Y';
    }
    for (int i = 71; i < 100; i++) {
        mat[i][i + 1] = mat[i + 1][i] = 'Y';
        mat[i][i - 30 + 1] = mat[i - 30 + 1][i] = 'Y';
    }
    scanf("%d", &k);
    int len = log2(k) + 1;
    for (int i = 1; i <= len; i++) {
        if (k % 2)
            mat[40 + i][11 + len - i] = mat[11 + len - i][40 + i] = 'Y';
        k /= 2;
    }
#ifndef DEBUG
    puts("100");
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 100; j++)
            putchar(mat[i][j]);
        puts("");
    }
#else
    int dis[maxn][maxn], ans = 0;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++)
            dis[i][j] = mat[i][j] == 'Y' ? 1 : inf;
    for (int k = 1; k <= 100; k++) {
        for (int i = 1; i <= 100; i++)
            for (int j = 1; j <= 100; j++) {
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
            }
    }
    for (int k = 3; k <= 100; k++) {
        if (dis[1][k] + dis[k][2] == len + 2) {
            ans++;
            printf("k--> %d dis[1][k] --> %d dis[k][2] --> %d\n", k, dis[1][k], dis[k][2]);
        }
    }
    //printf("min   ----> %d  ans --->   %d\n", p, ans);
    printf("min --> %d  ans ----> %d \n", dis[1][2], ans);
#endif
    return 0;
}
Ruby

CodeForces 195 C 上班题

Posted on

别说了,上班题,我比赛用c++ 写了一个半小时,晚上继续用c++写了两个小时,突然跟天海吹牛说,要是我会c++的正则表达式,这道题,妙了!
然后就说可以用脚本语言,我也只能勉为其难的用ruby写了。

推荐一个ruby在线正则表达式检测 网站

语法有些忘了……写的慢了点

题意:
模拟 try catch

思路:
无。

AC Code

#!/usr/bin/env ruby
# encoding: utf-8
n=gets.to_i

thlist = []
thid = []
trylist = []
flag=0

n.times do |id|
  str=gets.strip!
  next if flag == 1
  if /^try$/ =~ str
    trylist << id
  elsif /throw/ =~ str
    /(?<=\()\s*\w+\s*(?=\))/ =~ str
    thlist << $&.strip
    thid << id
  elsif /catch/ =~ str
    /(?<=\()\s*\w+\s*(?=,)/ =~ str
    if (pos=thlist.index($&.strip))!=nil && thid[pos] > trylist.last
      /(?<=\").+(?=\")/ =~ str
      puts $&
      flag=1
    end
    trylist.pop
  end
end

puts "Unhandled Exception" if flag == 0