题目大意

给你一个二分图，并告诉每个点的点权
要求二分图的最大独立集并使得权值最大，同时输出任意一组方案。

题解

是一道经典的二元关系最小割的问题。
我们要求二分图最大独立集，那么我们就可以考虑求最大匹配，即最大独立集=点数-最大匹配，具体证明为：

二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。——百度百科

为了方便计算答案，我们可以考虑求最小点覆盖（等于最大匹配），这就是一个最小割的问题了。
我们先考虑有关答案的事情。
题目问的是在满足独立集最大的前提下使得点权和最大。
那么说我们可以给每个 $w [i]$ 加上一个 $i n f$ ，并且保证这个 $inf\ge \sum w[i]$ 。
这是一个挺妙的做法，有什么好处呢？我们可以保证一种方案的 $w$ 值无论多大，只要这种方案的点数没有另外的方案的点数多，这种方案的答案肯定会更小。
由此，我们可以开始建图了。
首先，我们先给这个二分图黑白染色（就是一个dfs的事情），假设左边的点为白色，右边的点为黑色。
那么我们新建一个源点和汇点，源点给每个白点连边，边权为 $w$ ，每个黑点向汇点连边，边权同样为 $w$ 。然后对于每个限制（即白点和黑点），我们连一条边权为 $INF(INF>inf+w_{max})$ 的边。
然后我们去跑最小割。
设 $ans'=\sum w[i]$ ， $a n s = a n s^{'} ? 最大流$ 。
我们考虑如何统计答案：
第二个答案是很好处理的，即 $ans\ mod \ inf$ （显然）
现在我们考虑第一个（跟第三个一样）答案怎么做：
我的方法是把 $S$ 中左边的点+ $T$ 中右边的点和 $S$ 中右边的点+ $T$ 中左边的点的个数比较一下，然后输出。
但是题解中好像单输出了 $S$ 中左边的点+ $T$ 中右边的点，我也不是很明白，欢迎各位大佬来爆踩。

Code

#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
const int N=605;
const ll inf=4e9;
const ll INF=inf*100000LL;
struct node{
	int to,next;
	ll f;
}e[2*N*N];
int n,m,cnt,s,t;
int head[N],dep[N],cur[N],x[N*N],y[N*N],pd[N];
bool bz[N],bj[N][N],vis;
ll w[N],ans;
void add(int u,int v,ll f){
	e[++cnt].to=v;
	e[cnt].f=f;
	e[cnt].next=head[u];
	head[u]=cnt;
	return;
}
void doit(int u,int c){
	pd[u]=c;
	if (c==0) add(s,u,w[u]),add(u,s,0);
	else add(u,t,w[u]),add(t,u,0);
	for (int i=1;i<=n;++i)
		if (u!=i&&pd[i]==-1&&bj[i][u])
			doit(i,c^1);
	return;
}
bool bfs(){
	for (int i=0;i<=t;++i) dep[i]=1<<30,bz[i]=0,cur[i]=head[i];
	queue<int>q;
	bz[s]=1;
	dep[s]=0;
	q.push(s);
	while (!q.empty()){
		int u=q.front();
		q.pop();
		bz[u]=0;
		for (int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if (dep[v]>dep[u]+1&&e[i].f){
				dep[v]=dep[u]+1;
				if (!bz[v]){
					bz[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dep[t]!=(1<<30);
}
ll dfs(int u,ll flow){
	if (u==t){
		ans-=flow;
		return flow;
	}
	ll used=0;
	for (int i=cur[u];i;i=e[i].next){
		cur[u]=i;
		int v=e[i].to;
		if (dep[v]==dep[u]+1&&e[i].f){
			ll ff=dfs(v,min(flow,e[i].f));
			if (ff){
				used+=ff;
				e[i].f-=ff;
				e[i^1].f+=ff;
				if (used==ff) break;
			}
		}
	}
	return used;
}
void work(){
	while (bfs()){
		vis=1;
		while (vis) vis=0,dfs(s,INF-1);
	}
	return;
}
void find(int u){
	bz[u]=1;
	for (int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if (e[i].f&&!bz[v]) find(v);
	}
	return;
}
int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%lld",&w[i]),w[i]+=inf,ans+=w[i];
	cnt=1;
	for (int i=1;i<=m;++i){
		scanf("%d%d",&x[i],&y[i]);
		if (bj[x[i]][y[i]]) continue;
		bj[x[i]][y[i]]=bj[y[i]][x[i]]=1;
	}
	s=n+1;t=n+2;
	for (int i=1;i<=n;++i) pd[i]=-1;
	for (int i=1;i<=n;++i)
		if (pd[i]==-1) doit(i,0);
	for (int i=1;i<=m;++i){
		if (pd[x[i]]==1) x[i]^=y[i],y[i]^=x[i],x[i]^=y[i];
		add(x[i],y[i],INF);add(y[i],x[i],0);
	}
	work();
	for (int i=1;i<=t;++i) bz[i]=0;
	find(s);
	int ans1=0,ans2=0;
	for (int i=1;i<=n;++i) ans1+=(bz[i]^pd[i]);
	for (int i=1;i<=n;++i) ans2+=(bz[i]^pd[i])==0;
	printf("%d %lld\n",max(ans1,ans2),ans%inf);
	for (int i=1;i<=n;++i) printf("%d",ans1>=ans2?(bz[i]^pd[i]):((bz[i]^pd[i])==0));
	fclose(stdin);
	fclose(stdout);
	return 0;
}