胡伯涛的《最小割模型在信息学竞赛中的应用》写的真牛。

这道题是选择一些男孩和女孩参加party，邀请的男孩女孩之间不能有 8g，图就是个明显的二分图，就是选择一些点之间没有8g关系，就是二分匹配里的最大独立集，但是要求选出的点的权值最大，就是最小割模型里的最大点权独立集了，

最大点权独立集+最小点权覆盖集=图的总权值，这里跟二分匹配一样求出最小点权覆盖就可以，求出最小割后，从原点深搜，流量>0的边才可以走，搜到的左边的点都是要选的点，搜不到的右边的带点也是要选的，最小割就是我们要去掉点的权值。。

#include<stdio.h>

#include<string.h>

const int N=210;

const int inf=0x3fffffff;

int dis[N],head[N],gap[N],start,end,ans,num,vis[N],boy,girl,n,m;

struct edge

{

	int st,ed,flow,next;

}e[N*N];

void addedge(int x,int y,int w)

{

	e[num].st=x;e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;

	e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;

}

int dfs(int u,int minflow)

{

	if(u==end)return minflow;

	int i,v,f,flow=0,min_dis=ans-1;

	for(i=head[u];i!=-1;i=e[i].next)

	{

		if(e[i].flow>0)

		{

			v=e[i].ed;

			if(dis[v]+1==dis[u])

			{

				f=dfs(v,e[i].flow>minflow-flow?minflow-flow:e[i].flow);

				e[i].flow-=f;

				e[i^1].flow+=f;

				flow+=f;

				if(flow==minflow)break;

				if(dis[start]>=ans)return flow;

			}

			min_dis=min_dis>dis[v]?dis[v]:min_dis;

		}

	}

	if(flow==0)

	{

		if(--gap[dis[u]]==0)

		   dis[start]=ans;

		dis[u]=min_dis+1;

		gap[dis[u]]++;

	}

	return flow;

}

int isap()

{

	int maxflow=0;

	memset(dis,0,sizeof(dis));

	memset(gap,0,sizeof(gap));

	gap[0]=ans;

	while(dis[start]<ans)

	  maxflow+=dfs(start,inf);

	return maxflow;

}

void dfs1(int u)

{

	int i,v;

	for(i=head[u];i!=-1;i=e[i].next)

	{

		v=e[i].ed;

		if(vis[v]==1)continue;

		if(e[i].flow>0)

		{

			vis[v]=1;

			dfs1(v);

		}

	}

}

int main()

{

	int i,w,k,x,y,sum;

	while(scanf("%d%d%d",&n,&m,&k)!=-1)

	{

		memset(head,-1,sizeof(head));

		num=0;start=0;end=n+m+1;ans=end+1;sum=0;

		for(i=1;i<=n;i++)

		{

			scanf("%d",&w);

			sum+=w;

			addedge(start,i,w);

		}

		for(i=1;i<=m;i++)

		{

			scanf("%d",&w);

			sum+=w;

			addedge(i+n,end,w);

		}

		for(i=0;i<k;i++)

		{

			scanf("%d%d",&x,&y);

			addedge(x,n+y,inf);

		}

		printf("%d ",sum-isap());

		memset(vis,0,sizeof(vis));

		boy=girl=0;

		vis[start]=1;dfs1(start);

		for(i=1;i<=n;i++)

		   if(vis[i]==1)boy++;//源点能到达的男孩

		for(i=n+1;i<=n+m;i++)

			if(vis[i]==0)girl++;//源点不能到达的女孩

		printf("%d %d\n",boy,girl);

		for(i=1;i<=n;i++)

			if(vis[i]==1)

			{printf("%d",i);break;}

		for(i++;i<=n;i++)

			if(vis[i]==1)printf(" %d",i);

		printf("\n");

		for(i=n+1;i<=n+m;i++)

		{if(vis[i]==0)printf("%d",i-n);break;}

		for(i++;i<=n+m;i++)

			if(vis[i]==0)

			printf(" %d",i-n);

		printf("\n");

	}

	return 0;

}