树形DP

CodeForces 19E Fairy

Posted on

一道二分图性质的应用 + 树形DP ?

看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些

题意:
给你一个图,让你删除一条边,使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路:
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写,最后无奈去看题解了……

先整理一下判断思路:

  1. 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件
  2. 覆盖了所有的奇环,并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环,这个我还真没想到,但是在纸上画一画就是很显然的了,同时覆盖奇环和偶环的边删去后,两个环会变成一个新的环,偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现,随便生成一棵生成树,用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ,那么非树边必定不可能是满足条件的,因为非树边最多只能覆盖一个环,两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑,如果该非树边覆盖了奇环,则删之。
而对于树边,判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

void addEdge(int u, int v)
{
    edges[idx] = make_pair(v, head[u]);
    head[u] = idx++;
    edges[idx] = make_pair(u, head[v]);
    head[v] = idx++;
}

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}
二分图染色

洛谷 1155 双栈排序

Posted on

别多说了,神题。

写不来,看得是大佬的题解
很妙,没想到用二分图染色,但是二分图染色的模型的确很适合这个题目。

不过关键还是那个判定定理。

题意:
给你一个序列,要你用两个栈给它排序,问你这个序列是否能排序成功。

思路:
上面的链接很详细,我这里简单说一蛤。
首先必须注意到判定两个数必须在两个不同的栈的充要条件。

S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

我们首先用\( O( n^2 ) \) 的复杂度预处理出必须在两个栈的位置,并对其连边,再对其染色,对没有限制的优先放在第一个栈中因为要字典序最小

通过染色判定,不能形成二分图则输出0,否则模拟输出序列。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;

int ary[maxn];
int bmin[maxn];
int color[maxn];
int st1[maxn], st2[maxn], t1, t2;

vector<int> G[maxn];

bool dfs(int u, int c)
{
    color[u] = c;
    int sz = G[u].size(), v;
    for (int i = 0; i < sz; i++) {
        v = G[u][i];
        if (!color[v] && !dfs(v, 3 - c))
            return false;
        else if (color[v] == c)
            return false;
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", ary + i);
    bmin[n] = inf;
    for (int i = n - 1; i >= 0; i--)
        bmin[i] = min(bmin[i + 1], ary[i]);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (ary[i] < ary[j] && bmin[j + 1] < ary[i])
                G[i].push_back(j), G[j].push_back(i);
    for (int i = 0; i < n; i++)
        if (!color[i] && !dfs(i, 1)) {
            puts("0");
            return 0;
        }
    int cur = 1;
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) {
            printf("a ");
            st1[++t1] = ary[i];
        } else {
            printf("c ");
            st2[++t2] = ary[i];
        }
        while (st1[t1] == cur || st2[t2] == cur) {
            if (st1[t1] == cur)
                printf("b "), t1--;
            else
                printf("d "), t2--;
            cur++;
        }
    }
    return 0;
}
稳定婚姻问题

稳定婚姻问题入门

Posted on

第一次看了理论之后自己敲代码直接 1A !!!蛤蛤蛤蛤!!! 嗝~~

稳定婚姻问题的定义与求解方法详见百度百科
中文维基上写的比较简单。

简单说一下个人理解与解法。个人感觉还是挺有趣的。

稳定婚姻问题是构建在男女双方的二分图基础上的。如果对于现有的一个男女匹配,存在一个男人 a 比起现在的妻子女人 a 更喜欢 女人 b 。而与此同时,女人 b 比起现在的丈夫男人 b ,更喜欢男人 a 。那么男人 a 与 女人 b 很可能会出轨。我们称这个婚姻匹配是不稳定的。
反之,如果不存在这个会出轨的男女匹配,则称这个婚姻匹配是稳定的。

稳定婚姻问题的求法在上面的中文维基上有伪代码,我也基本上按照这个理论敲的。
略为详细的步骤如下:
1. 为每一个男性与女性确定一个各自的异性在自己眼里的排名。但是记录方式不太一样,根据我的写法,男性需要记录的是排名第几是那个女性,女性需要记录的是这个男性排第几。
2. 将每个男性加入队列。尝试为每个男性按排名配偶,如果这个女性暂时没有配偶,那么暂时进行匹配。否则,与她现在的配偶进行比较。给女性出轨的机会。
3. 如果一个女性出轨了,那么她的丈夫放回队列。

其实就是不断出轨的算法啦,允许他们不断出轨,到不想出轨。

算法复杂度 \( O( n^2 ) \)

下面是一个入门题 HDU 1435 Stable Match

题意:
这里的男女改成了发射站与接收站,喜欢程度改成了距离与容量。距离优先,再是容量。
让你求出一个稳定婚姻。

思路:
上面说的很清楚了啦。具体实现看代码。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 205;

int n;
int mrank[maxn][maxn], wrank[maxn][maxn];
int wlink[maxn];
double dis[maxn][maxn];

queue<int> que;

struct People {
    int id, cap;
    double dis;
    bool operator<(const People& a) const
    {
        if (dis != a.dis)
            return dis < a.dis;
        return cap > a.cap;
    }
} peo[maxn];

struct Point {
    int cap;
    double x, y, z;
    void input() { scanf("%*d %d %lf %lf %lf", &cap, &x, &y, &z); }
} man[maxn], woman[maxn];

inline double two(double x) { return x * x; }
inline double getDis(int a, int b) { return two(man[a].x - woman[b].x) + two(man[a].y - woman[b].y) + two(man[a].z - woman[b].z); }

void getRank()
{
    range(i, 1, n)
    {
        range(j, 1, n) peo[j] = (People){ j, woman[j].cap, dis[i][j] };
        sort(peo + 1, peo + n + 1);
        range(j, 1, n) mrank[i][j] = peo[j].id;

        range(j, 1, n) peo[j] = (People){ j, man[j].cap, dis[j][i] };
        sort(peo + 1, peo + n + 1);
        range(j, 1, n) wrank[i][peo[j].id] = j;
    }
}

void stableMatch()
{
    range(i, 1, n)
    {
        que.push(i);
        wlink[i] = -1;
    }
    while (!que.empty()) {
        int male = que.front();
        que.pop();
        range(j, 1, n)
        {
            int female = mrank[male][j];
            if (female == -1)
                continue;
            mrank[male][j] = -1;
            if (wlink[female] == -1) {
                wlink[female] = male;
                break;
            } else if (wrank[female][wlink[female]] > wrank[female][male]) {
                que.push(wlink[female]);
                wlink[female] = male;
                break;
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        range(i, 1, n) man[i].input();
        range(i, 1, n) woman[i].input();
        range(i, 1, n) range(j, 1, n) dis[i][j] = sqrt(getDis(i, j));
        getRank();
        stableMatch();
        range(i, 1, n) printf("%d %d\n", wlink[i], i);
    }
    return 0;
}
多重匹配

HDU 3605 Escape

Posted on

多重匹配模板题……也是从薛昊那偷来的题……

貌似有更好的做法……看到了什么二进制压缩什么的……

这题数据很大,时间卡的很紧,使得我对模板使用了解更深了一点。

题意:
地球上有n个人要移民,有m的星球可以提供移民,这些人都很挑剔,只去自己感兴趣的星球,问是否存在一个方案使得每个人都能去自己感兴趣的星球。
每个星球容纳人数有限。
人数1e5,星球数 10。

思路:
二分图多重匹配裸题。这里如果你对模板使用比较了解肯定是一发水过的……

这里要对数组强调一下。 记 左元数组 l ,右元数组 r

  • mat[n][m] 二维可达矩阵。
  • link[m][n] 二维连接矩阵,记录每个 r 元素 连接的 l 元素
  • vis[m] 单次dfs的访问记录数组
  • vlink[m] 记录每个 r 元素连接的 l 元素数量
  • num[m] 记录每个 r 元素的限制数量

简单说,只有可达矩阵是n开头的!!!!!!

靠着输入挂800+ms……

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

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

using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 12;
const int inf = 0x3f3f3f3f;

int n, m;
int mat[maxn][maxm];
int link[maxm][maxn];
int vlink[maxm], vis[maxm], num[maxm];

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

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

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

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        each(i, n) each(j, m) scan_d(mat[i][j]);
        each(i, m) scan_d(num[i]);
        if (hungary())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
多重匹配

POJ 3189 Steady Cow Assignment

Posted on

二分图多重匹配第二题,提前再说一句,二分图匹配用网络流均可解
因为受了ysk学长博客的影响,开始习惯用宏定义写代码,有点不习惯,搞得我在控制范围上浪费了一些时间。

题意:
n头牛,m个牛棚,每头牛各自有各自喜欢的牛棚,给出喜欢的牛棚顺序,每个牛棚容量,要求他们的喜欢范围最小。(就是所住牛棚的最大喜欢值 - 最小喜欢值 最小)

思路:
二分牛棚数 ,并枚举范围起点,判断可行性 这么暴力?

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#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 range(i, st, en) for (int(i) = (st); (st) <= (en); (st)++)
#define rrange(i, st, en) for (int(i) = (st); (st) >= (en); (st)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 30;
int n, m, maxcap;
bool vis[maxn];
int link[maxm][maxn], vlink[maxm], mat[maxn][maxm], num[maxm];

bool dfs(int u, int st)
{
    each(i, m) if (i >= st && i < maxcap + st)
    {
        int v = mat[u][i] - 1;
        if (vis[v])
            continue;
        vis[v] = true;
        if (vlink[v] < num[v]) {
            link[v][vlink[v]++] = u;
            return true;
        }
        each(j, vlink[v]) if (dfs(link[v][j], st))
        {
            link[v][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary(int mid)
{
    maxcap = mid;
    each(st, m - mid + 1)
    {
        fill(vlink, 0);
        bool flag = true;
        each(i, n)
        {
            fill(vis, false);
            if (!dfs(i, st)) {
                flag = false;
                break;
            }
        }
        if (flag)
            return true;
    }
    return false;
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        each(i, n)
            each(j, m)
                scanf("%d", &mat[i][j]);
        each(i, m)
            scanf("%d", &num[i]);
        int l = 1, r = m, 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;
}
多重匹配

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;
}
带权最大匹配

HDU 2853 Assignment

Posted on

最近在水KM算法 只要把KM理解了 至今写到的大部分都是水题

唯独这题让我写了很长时间 看了其他人的博客才明白什么叫建图的巧妙和重要性

题意 有n家公司和m个任务 所有任务和公司都已经匹配好了 要求在尽量保留原有匹配的基础上 求得最优匹配 输出改变的数量 和 改变后增加的权值

巧妙的思路来了 首先对于所有输入的权值增大K倍 这里的K必须大于n 再对原匹配的权值都加 1 这样 原匹配的优先级将大于其他匹配

再套模板 这时出来的结果 将是匹配权值数的K倍再加上原匹配的数目 (所以这里就体现了K大于n的原因了 若是K小于n 那么大于K的部分将可能成为原匹配数目,结果将乱套………………

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;
const int maxn=55;
const int inf=0x3f3f3f3f;
int cnum,mnum;
int linky[maxn],lx[maxn],ly[maxn];
bool visx[maxn],visy[maxn];
int g[maxn][maxn],slack[maxn];

bool dfs(int x)
{
    visx[x]=true;
    for(int y=1;y<=mnum;y++)
    {
        if(visy[y]) continue;
        int t=lx[x]+ly[y]-g[x][y];
        if(t==0)
        {
            visy[y]=true;
            if(linky[y]==-1||dfs(linky[y]))
            {
                linky[y]=x;
                return true;
            }
        }
        else if(slack[y]>t) slack[y]=t;
    }
    return false;
}

int KM()
{
    memset(linky,-1,sizeof linky);
    memset(ly,0,sizeof ly);
    for(int i=1;i<=cnum;i++)
    {
        lx[i]=-inf;
        for(int j=1;j<=mnum;j++)
            if(g[i][j]>lx[i]) lx[i]=g[i][j];
    }
    for(int x=1;x<=cnum;x++)
    {
        for(int i=1;i<=mnum;i++) slack[i]=inf; 
        while(true)
        {
            memset(visx,false,sizeof visx);
            memset(visy,false,sizeof visy);
            if(dfs(x)) break;
            int d=inf;
            for(int i=1;i<=mnum;i++)
                if(!visy[i]&&d>slack[i]) d=slack[i];
            for(int i=1;i<=cnum;i++)
                if(visx[i]) lx[i]-=d;
            for(int i=1;i<=mnum;i++)
                if(visy[i]) ly[i]+=d;
                else slack[i]-=d;
        }
    }
    int result=0;
    for(int i=1;i<=mnum;i++)
    {
        if(linky[i]>-1)
            result+=g[linky[i]][i];
    }
    return result;
}

int main()
{
    int eff;
    while(scanf("%d%d",&cnum,&mnum)!=EOF)
    {
        int prenum=0,m;
        for(int i=1;i<=cnum;i++)
            for(int j=1;j<=mnum;j++)
            {
                scanf("%d",&eff);
                g[i][j]=eff*100;
            }
        for(int i=1;i<=cnum;i++)
        {
            scanf("%d",&m);
            prenum+=g[i][m];
            g[i][m]++;
        }
        int ans=KM();
        printf("%d %d\n",cnum-ans%100,ans/100-prenum/100);

    }
    return 0;
}