GYM 100523 I【二分图的最大点权独立集】

心已赠人 2022-08-04 04:04 171阅读 0赞

## Intelligence Quotient ILO ##

At the University of Byteland one can only study maths and computer science. Currently there are n maths  
students and m computer science students. These majors are so hard to study that nobody studies both of  
them at the same time.  
Byteasar is the rector of the university. He would like to form a team of students which will solve all the  
hardest problems of mankind. Since he knows the IQ of each student, he has decided to form a team with the  
largest possible sum of IQs of its members.  
However, IQ is not everything. That is why the rector would like all members of the team to know each  
other. It is known that all maths students know each other. And similarly, each computer science student  
knows every other student majoring in computer science.  
Help the rector by writing a program that will help him form a team of students with the largest possible  
sum of IQs in which all the members know each other.

### Input ###

The first line of the input contains three integers n, m and k (1≤n;m≤400,0≤k≤n×m) which denote  
the number of maths students, the number of computer science students and the number of pairs of students  
from different majors that know each other, respectively.  
Each of the following k lines describes one pair of acquaintances: the i-th of these lines contains two integers  
ai and bi (1≤ai≤n,1≤bi≤m) denoting an index of a maths student and an index of an computer science  
student from the i-th pair. The maths students are indexed with integers starting from 1 and so are the  
computer science students.  
The following line contains n integers in the range \[1; 109\], which represent the IQs of the subsequent maths  
students. The next line contains m integers representing the IQs of the computer science students, in a similar  
format.

### Output ###

The first line of the output should contain one integer equal to the maximum sum of IQs in a team satisfying  
Byteasar’s requirements.  
The second line should contain one integer — the number of maths students that Byteasar should choose.  
The third line should contain the indices of these students, listed in any order. If there are no maths students  
in the team, an empty line should be printed.  
The following two lines should describe the indices of computer science students assigned to the team, in  
a similar format.  
If there are multiple optimal solutions, your program should output any one of them.

### Example ###

For the input data:  
3 2 3  
1 1  
2 1  
2 2  
1 3 1  
1 2  
a correct result is:  
6  
1  
2  
2  
1 2

论文题：  
胡波涛论文《最小割模型在信息学竞赛中的应用》中二分图的最大点权独立集。  
现将所以得IQ加起来，然后将不认识的人连边，跑最大流。  
再用∑IQ−Maxflow就是最大的组IQ值

方案：  
用bfs搜索残留网络，能用的点是左边能够访问的点，右边不能访问的点。  
一开始用ISAP怎么都不懂怎么搜比较好（其实也不算太难，用dfs标记就好 ），最好换了Dinic，直接BFS就行了。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<50
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=1010;
    const int MAXM=400000;
    
    struct Dinic
    {
        struct Edge
        {
            int to,next;
            ll f;
        } e[MAXM];
        int n,src,sink;
        int head[MAXN];
        int tot;
    
        void addedge(int u,int v,ll c)
        {
            e[++tot].to=v;
            e[tot].f=c;
            e[tot].next=head[u];
            head[u]=tot;
            e[++tot].to=u;
            e[tot].f=0;
            e[tot].next=head[v];
            head[v]=tot;
        }
    
        void Resize(int n)
        {
            this->n=n;
        }
    
        void Clear()
        {
            CLR(head,-1);
            tot=1;
        }
    
        bool vis[MAXN];
        int dist[MAXN];
    
        void bfs()
        {
            CLR(dist,0);
            queue<int> que;
            vis[src]=true;
            que.push(src);
            while(!que.empty())
            {
                int u=que.front();que.pop();
                for(int i=head[u]; ~i; i=e[i].next)
                {
                    if(e[i].f>0 && !vis[e[i].to])
                    {
                        que.push(e[i].to);
                        dist[e[i].to]=dist[u]+1;
                        vis[e[i].to]=true;
                    }
                }
            }
        }
    
        ll dfs(int u,ll delta)
        {
            if(u==sink || delta==0)
                return delta;
            else
            {
                ll ret=0;
                for(int i=head[u]; ~i; i=e[i].next)
                    if(e[i].f && dist[e[i].to]==dist[u]+1)
                    {
                        ll dd=dfs(e[i].to,min(e[i].f,delta));
                        e[i].f-=dd;
                        e[i^1].f+=dd;
                        delta-=dd;
                        ret+=dd;
                    }
                return ret;
            }
        }
    
        ll MaxFlow(int s,int t)
        {
            ll ret=0;
            this->src=s;this->sink=t;
            while(1)
            {
                CLR(vis,0);
                bfs();
                if(!vis[sink])
                    return ret;
                ret+=dfs(src,LLINF);
            }
        }
    
        void print()
        {
            puts("GRAPH:");
            for(int i=0;i<n;i++)
            {
                printf("%d ->",i);
                for(int j=0;~j;j=e[j].next)
                    printf("%d(%d) ",e[j].to,e[i].f);
                putchar('\n');
            }
        }
    
    };
    
    Dinic g;
    
    int n,m,k;
    ll IQ;
    int ma[MAXN/2][MAXN/2];
    ll sum=0;
    
    int main()
    {
        read(n),read(m),read(k);
        g.Clear();
        g.Resize(n+m+2);
        for(int i=0,u,v;i<k;i++)
        {
            read(u),read(v);
            ma[u][v]=1;
        }
        for(int i=1;i<=n;i++)
        {
            read(IQ);sum+=IQ;
            g.addedge(0,i,IQ);
        }
        for(int i=1;i<=m;i++)
        {
            read(IQ);sum+=IQ;
            g.addedge(i+n,n+m+1,IQ);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(!ma[i][j])
                {
                    g.addedge(i,j+n,LLINF);
                }
    
        ll ret=g.MaxFlow(0,n+m+1);
        write(sum-ret),putchar('\n');
        //g.print();
        g.bfs();
        int cnt=0,cnt2=0;
        for(int i=1;i<=n;i++)
            if(g.vis[i])
                cnt++;
        for(int i=1;i<=m;i++)
            if(!g.vis[i+n])
                cnt2++;
        write(cnt),putchar('\n');
        for(int i=1;i<=n;i++)
            if(g.vis[i])
                write(i),putchar(' ');
        putchar('\n');
        write(cnt2),putchar('\n');
        for(int i=1;i<=m;i++)
            if(!g.vis[i+n])
                write(i),putchar(' ');
        putchar('\n');
    
        return 0;
    }