scu oj 4442 Party(2015年四川省acmプログラミングコンテスト)★★

転載先:http://blog.csdn.net/u012127882/article/details/47397919
あるカエルはお茶を饮んで、あるカエルは红茶しか饮むことができなくて、あるカエルは绿茶しか饮むことができなくて、あるカエルの红茶绿茶はすべて饮むことができます.今mはカエルの間に矛盾があって、矛盾のあるカエルは彼らが同じお茶を飲むことができなくて、カエルごとに、彼にw[i]金貨をあげることができて、彼にお茶を飲まないで、彼はいかなるカエルと矛盾しません.少なくともいくらをあげて彼らの間に矛盾がないようにしなければならないのか.この問題にはもう一つ重要な情報がありますが、最初は見ていませんでした.この言葉は——「
Luckily, frogs can be divided into 
2
 groups such that no two frogs in the same group dislike each other.」実はこの言葉はとても重要で、その意味はこの矛盾関係図に奇環が存在しないことで、2分図論です. 
 この条件ができた.私たちは今、お茶を1つしか飲めないカエルを考えています.赤と緑の間には矛があっても影響しないので、赤と赤、緑と緑の間の矛盾関係だけを考えています.2種類とも飲めるカエルを考えると、赤も赤も緑も単独で最大点権独立集を求める.2点図なので、簡単に求めることができます.今1匹の2种类のお茶のすべて饮むことができるカエルを考えて、ここは肝心で、私の解法はこのカエルを2つの点に分解して、1つの点は彼と红茶を代表して、1つの点は彼と绿茶を代表して、まずこの2つの点は同时に存在することができなくて、それでは必然的に縁があって、それからもしこの青蛙とその他の红茶のカエルと矛盾している関系があるならば、では、対応はこのカエルが赤い点を飲むのと、カエルが赤い点を飲むのとが同時に存在しないことであり、他の状況は実際には似たような分析である.このように分割して矛盾関係図を作成した後、実際には2点図であり、現在は最大点権を選択した点がこれらの点の間に矛盾関係がないようにしている.実は点権最大独立セットで、点権最小カバーを求めるモデルに変換すると、簡単に解くことができます...こんなに長く考えていたら、やはり神建図だった.実は主に分解点です.

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
using namespace std;
const int mmax  = 2010;
const int inf = 0x3fffffff;

struct node
{
    int flow;
    int en;
    int next;
}E[100*mmax];
int p[mmax];
int num;
void init()
{
    memset(p,-1,sizeof p);
    num=0;
}
void add(int st,int en,int flow)
{
    E[num].en=en;
    E[num].flow=flow;
    E[num].next=p[st];
    p[st]=num++;
    E[num].en=st;
    E[num].flow=0;
    E[num].next=p[en];
    p[en]=num++;
}

int d[mmax];
int cur[mmax];
bool vis[mmax];
bool bfs(int st,int en)
{
    memset(vis,0,sizeof vis);
    d[st]=0;
    vis[st]=1;
    queueq;
    q.push(st);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=p[x]; i+1; i=E[i].next)
        {
            int v=E[i].en;
            if(!vis[v]&&E[i].flow)
            {
                vis[v]=1;
                d[v]=d[x]+1;
                q.push(v);
            }
        }
    }
    return vis[en];
}
int dfs(int st,int en,int  flow)
{
    if(st==en||flow==0)
        return flow;
    int f=0,dd;
    for(int &i=cur[st]; i+1;i=E[i].next)
    {
        int v=E[i].en;
        if(d[st]+1==d[v]&&(dd=dfs(v,en,min(flow,E[i].flow)))>0)
        {
            E[i].flow-=dd;
            E[i^1].flow+=dd;
            flow-=dd;
            f+=dd;
            if(flow==0)
                break;
        }
    }
    return f;
}
int dinic(int st,int en,int n)
{
    int flow=0;
    while(bfs(st,en))
    {
        for(int i=0;i<=n;i++)
            cur[i]=p[i];
        flow+=dfs(st,en,inf);
    }
    return flow;
}

vectore[mmax];
int fg[mmax];
int w[mmax];
void dfs(int u)
{
    int SZ=e[u].size();
    for(int i=0;i