A Plug for UNIX最大流

3755 ワード

/*       m   ，n   ，tt    ，                。                。
         1.    n         。       。                       'X，      ，     。
          map   。   。              。    http://www.cnblogs.com/longdouhzt/archive/2011/09/03/2165860.html*/
#include 
#include 
#include 
#include 
#include 
#include 
#define SETZR(a) memset(a,0,sizeof(a))
using namespace std;
const int MAXM = 100000;
const int MAXN = 305;
const int INF = 1000000000;
struct record
{
    int v, f, next;
} edge[MAXM];

int n, m, s, t, cas, cl,k,ca;
int pointer[MAXN], dis[MAXN], vh[MAXN];
int his[MAXN], di[MAXN], pre[MAXN];
map maper;
void add(int a, int b, int f)
{
    cl++;
    edge[cl].next = pointer[a];
    edge[cl].v = b;
    edge[cl].f = f;
    pointer[a] = cl;
    cl++;
    edge[cl].next = pointer[b];
    edge[cl].v = a;
    edge[cl].f = 0;
    pointer[b] = cl;
}
void maxflow()
{
    vh[0] = n;
    for (int i = 0; i < n; i++) di[i] = pointer[i];
    int i = s, aug = INF, flow = 0;
    bool flag = 0;
    while (dis[s] < n)
    {
        his[i] = aug;
        flag = 0;
        int p = di[i];
        while (p != 0)
        {
            if ((edge[p].f > 0) && (dis[edge[p].v] + 1 == dis[i]))
            {
                flag = 1;
                di[i] = p;
                aug = min(aug, edge[p].f);
                pre[edge[p].v] = p;
                i = edge[p].v;
                if (i == t)
                {
                    flow += aug;
                    while (i != s)
                    {
                        edge[pre[i]].f -= aug;
                        edge[pre[i]^1].f += aug;
                        i = edge[pre[i]^1].v;
                    }
                    aug = INF;
                }
                break;
            }
            p = edge[p].next;
        }
        if (flag) continue;
        int min = n - 1;
        p = pointer[i];
        while (p != 0)
        {
            if ((edge[p].f > 0) && (dis[edge[p].v] < min))
            {
                di[i] = p;
                min = dis[edge[p].v];
            }
            p = edge[p].next;
        }
        --vh[dis[i]];
        if (vh[dis[i]] == 0) break;
        dis[i] = min + 1;
        ++vh[dis[i]];
        if (i != s)
        {
            i = edge[pre[i]^1].v;
            aug = his[i];
        }
    }
    if(ca==1) printf("
");
    ca=1;
    printf("%d
", m-flow);
}
int main()
{
    scanf("%d", &cas);
    ca=0;
    while (cas--)
    {
        cl = 1;
        SETZR(dis);
        SETZR(vh);
        SETZR(pointer);
        scanf("%d",&n);
        maper.clear();
        string a,b;
        for(int i=1;i<=n;i++)
        {
            cin >> a;
            maper[a]=i;
        }
        scanf("%d",&m);
        int tt=n;//tt        
        for(int i=1;i<=m;i++)
        {
            cin >> a >> b;
            add(0,i,1);
            if(maper.find(b)==maper.end())
            maper[b]=++tt;
            add(i,m+maper[b],1);
        }
        int k;
        scanf("%d",&k);
        maper["X"]=n+1;
        for(int i=1;i<=k;i++)
        {
            cin >> a >> b;
            if(maper.find(a)==maper.end())
            maper[a]=++tt;
            if(maper.find(b)==maper.end())
            maper[b]=++tt;
            add(maper[a]+m,maper[b]+m,INF);
        }
        s=0;
        t=m+tt+1;
        for(int i=1;i<=n;i++)
        add(m+i,t,1);
        for(int i=1;i<=m;i++)
        add(s,i,1);
        n=m+tt+2;
        maxflow();
    }
    return 0;
}

perl文字列の数値でソート

magentoプラグインのアンインストールの実用的な方法