sgu 210

KM ，把王子放在二分圖 X 側，妹子放在Y側，邊權為 (Ai)2 做 KM 即可，

具體實作時我把王子放在二分圖 Y 側，妹子放在X側，這樣就更容易輸出答案了。

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<utility>
#include<iostream>
#include<algorithm>

const int maxn = , INF = ;

int n, a[maxn];
int w[maxn][maxn];
bool visx[maxn], visy[maxn];
int slack[maxn], lx[maxn], ly[maxn];
int linky[maxn];

void init()
{
    std::cin >> n;
    for(int i = ; i <= n; i++)
        std::cin >> a[i];
    for(int i = , num; i <= n; i++)
    {
        std::cin >> num;
        for(int j = , to; j <= num; j++)
            std::cin >> to, w[to][i] = a[i]*a[i];
    }
}
bool find(int x)
{
    visx[x] = true;

    for(int y = ; y <= n; y++)
        if(!visy[y])
        {
            int dec = lx[x] + ly[y] - w[x][y];

            if(!dec)
            {
                visy[y] = true;
                if(!linky[y] || find(linky[y]))
                {
                    linky[y] = x;
                    return true;
                }
            }
            slack[y] = std::min(slack[y], dec);
        }
    return false;   
}
void KM()
{
    memset(lx,,sizeof(lx));
    memset(ly,,sizeof(ly));
    memset(linky,,sizeof(linky));

    for(int i = ; i <= n; i++)
        for(int j = ; j <= n; j++)
            lx[i] = std::max(lx[i],w[i][j]);

    for(int i = ; i <= n; i++)
    {
        memset(slack,INF,sizeof(slack));

        while(true)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));

            if(find(i)) break;

            int d = INF;

            for(int i = ; i <= n; i++)
                if(!visy[i]) d = std::min(slack[i], d);
            for(int i = ; i <= n; i++)
            {
                if(visx[i]) lx[i] -= d; 
                if(visy[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
}
void prt()
{
    for(int i = ; i <= n; i++)
        std::cout << (w[linky[i]][i]?linky[i]:) << ' ';
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("sgu210.in","r",stdin);
    freopen("sgu210.out","w",stdout);
#endif

    init(), KM(), prt();

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
#endif
    return ;
}