POJ 1486二分図最大マッチング必要マッチング

本題の意味はすべての必要なマッチングを出力することですが、満のマッチングでなければならないとは言っていないようです.
本題で必要マッチングとは、すべての最大マッチングで1つの数字が同じアルファベットにマッチングすることを意味します.では、この数字とアルファベットのマッチングは必要です.
使用する方法は、エッジを削除し、まず最大マッチングを行い、その後、各数字に対して、マッチングしたエッジを削除した図の中で拡張路を探す操作を行い、拡張路を見つけることができれば.この数字の一致が一意ではないことを示します.
そうでなければ出力します.
また、この問題は隣接マトリクスで行うのが望ましい.数字が小さく、エッジを削除するときに操作が便利だからだ.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 100005
#define MAXM 320005
#define INF 100000007
using namespace std;
struct node
{
    int x1, x2, y1, y2;
}p[30];
int g[30][30], link[30];
bool vis[30];
int n;
int dfs(int u)
{
    for(int v = 0; v < n; v++)
        if(g[u][v] && !vis[v])
        {
            vis[v] = 1;
            if(link[v] == -1 || dfs(link[v]))
            {
                link[v] = u;
                return 1;
            }
        }
    return 0;
}
int solve()
{
    int ans = 0;
    memset(link, -1, sizeof(link));
    for(int i = 0; i < n; i++)
    {
        memset(vis, 0, sizeof(vis));
        ans += dfs(i);
    }
    return ans;
}
int main()
{
    int cas = 0;
    while(scanf("%d", &n) != EOF && n)
    {
        if(cas) printf("
");
        printf("Heap %d
", ++cas);
        for(int i = 0; i < n; i++) scanf("%d%d%d%d", &p[i].x1, &p[i].x2, &p[i].y1, &p[i].y2);
        memset(g, 0, sizeof(g));
        int x, y;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", &x, &y);
            for(int j = 0; j < n; j++)
                if(x > p[j].x1 && x < p[j].x2 && y > p[j].y1 && y < p[j].y2)
                    g[i][j] = 1;
        }
        solve();
        int flag = 0;
        for(int i = 0; i < n; i++)
        {
            int tmp = link[i];
            link[i] = -1;
            g[tmp][i] = 0;
            memset(vis, 0, sizeof(vis));
            if(!dfs(tmp))
            {
                if(flag) printf(" ");
                printf("(%c,%d)", 'A' + i, tmp + 1);
                flag = 1;
                link[i] = tmp;
            }
            g[tmp][i] = 1;
        }
        if(!flag) printf("none
");
        else printf("
");
    }
    return 0;
}