UVALive 6322 最大匹配...

/*
 *e...大概明白了。首先用最大匹配看看是不是存在符合题意的匹配。然后呢。对枚举找到每个位置符合的字母里最小的那个。
 *判断是否能构成最大匹配。直到找完最后一个位置输出就好了。、

 *还是有些不理解最大匹配匈牙利算法的过程。而且这个题是最大匹配。也没想到。
 */

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 110

int g[N][N]; // 图的存储方式。矩阵。
int n; //二分图两个顶点集 本题个数相等
int vis[N]; //判断V2中的点是否已经被搜索过。一次寻找最大匹配中.
int viss[N]; // 判断V2中的点是不是已经被匹配到其它位置。所有的最大匹配过程都包括。
int link[N]; // 记录V2中的点和谁匹配了。
int m; // 最大匹配数；
int len; // 还未匹配的长度
char str[N], s[N];
int ans[N]; //保存每个位置匹配的字符对应的位置。

void init()
{
    memset(vis, 0, sizeof(vis));
    memset(viss, 0, sizeof(viss));
    memset(link, 0, sizeof(link));
    memset(g, 0, sizeof(g));
    memset(ans, 0, sizeof(ans));
    m  = 0;
}

void build()
{
    cin >> str+1;
    n = strlen(str+1);
    sort(str+1, str+1+n);
    for (int i=1; i<=n; ++i)
    {
        cin >> s;
        int len2 = strlen(s);
        for (int j=1; j<=n; ++j)
        {
            for (int k=0; k<len2; ++k)
            {
                if (str[j] == s[k])
                    g[i][j] = 1;  // 建图。我没想到这样建。
            }
        }
    }
}

int dfs(int x)
{
    for (int y=1; y<=n; ++y)
    {
        if (g[x][y] && !vis[y] && !viss[y])  // 如果x和y有边。而且y未被搜索和匹配.
        {
            vis[y] = 1;  // 标记已被搜索过.
            if (link[y] == 0 || dfs(link[y]))  //如果y未被匹配。或者y匹配的节点可以找到增广路。（为什么这也算是匹配成功呢。那和这个节点匹配的怎么办）
            {
                link[y] = x;    //当前匹配成功。
                return 1;
            }
        }
    }
    return 0;
}

void max_m()
{
    for (int x=1; x<=n; ++x)
    {
        memset(vis, 0, sizeof(vis)); // 清空上次搜索时的标记。
        if (dfs(x))
            m++;
    }
    return ;
}

int match()
{
    int anss = 0;
    memset(link, 0, sizeof(link));
    for (int x=1; x<=n; ++x)
    {
        if (ans[x]) continue;
        memset(vis, 0, sizeof(vis));
        if (dfs(x)) anss++;
    }
    return anss == len;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        init();
        build();
        max_m();
        if (m  < n)
        {
            cout << "NO SOLUTION\n";
            continue;
        }
        len = n;
        for (int i=1; i<=n; ++i) // 遍历每个位置的最小字符 用最大匹配判断是否可行。
        {
            for (int j=1; j<=n; ++j)
            {
                if (!viss[j] && g[i][j]) // 没有被其它位置匹配。而且和当前位置有边。
                {
                    ans[i] = j;
                    len--;
                    viss[j] = 1;
                    if (match()) break; // 当前位置成功。继续匹配下一个位置。
                    viss[j] = 0; //如果不成功。回溯。
                    len++;
                }
            }
        }
        for (int x=1; x<=n; ++x)
        {
            cout << str[ans[x]];
        }
        cout << endl;
    }
    return 0;
}