简要の题意
求二分图 最大权 最大独立集 的方案。
\(n\le 500\)
思路
二分图最大权独立集很好做，二分图最大独立集也很好做。
考虑 双关键字排序 中第一个关键字无穷大于第二个关键字的优先级。
所以可以令点的数量带来的流量远大于权值带来的流量。
\(+\infty\) 即可。
构造方案直接按求割做。
CODE
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#define reg register
#define uni unsigned
#define ll long long
using namespace std;
const int N=2010,FSIZE=1<<26;
const ll Inf=1000000000,INF=0x7f7f7f7f7f7f7f7f;
int n,m,h[N],a[N],last,w[N],d[N],cur[N],sum,cl[N];
ll b[N*N][3];
vector<int> T[N];
bool vis[N];
struct edge{
int x,y;
}e[N*N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
for(;47>*InF||*InF>58;++InF);
for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
void add(int x,int y,ll u){
b[last][0]=a[x];
b[a[x]=last][1]=y;
b[last++][2]=u;
}
void Add(int x,int y,ll u){
add(x,y,u);
add(y,x,0);
}
bool bfs(){
memset(w,127,sizeof(w));
for(reg int h=0,t=w[0]=0;h<=t;h++){
cur[d[h]]=a[d[h]];
for(reg int i=a[d[h]];~i;i=b[i][0]){
if(w[b[i][1]]>w[d[h]]+1&&b[i][2]){
w[b[i][1]]=w[d[h]]+1;
d[++t]=b[i][1];
}
}
}
return(w[n+1]<0x7f7f7f7f);
}
ll dfs(int now,ll flow){
if(now==n+1||!flow)
return(flow);
ll used=0,aflow;
for(reg int &i=cur[now];~i;i=b[i][0]){
if(w[b[i][1]]==w[now]+1&&b[i][2]&&(aflow=dfs(b[i][1],min(b[i][2],flow-used)))){
b[i][2]-=aflow;
b[i^1][2]+=aflow;
used+=aflow;
if(used==flow) break;
}
}
if(used==0) w[now]=0;
return(used);
}
ll dinic(){
reg ll maxflow=0;
for(;bfs();maxflow+=dfs(0,INF));
return(maxflow);
}
void find(reg int x){
vis[x]=1;
for(reg int i=a[x];~i;i=b[i][0]){
if(b[i][2]&&!vis[b[i][1]]) find(b[i][1]);
}
}
void color(reg int x,reg int c){
cl[x]=c;
for(reg vector<int>::iterator i=T[x].begin();i!=T[x].end();++i)
if(!~cl[*i]) color(*i,c^1);
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
fread(BuF,1,FSIZE,stdin);
read(n);read(m);
for(reg int i=0;i<n;read(h[++i]));
memset(a,-1,sizeof(a));
memset(cl,-1,sizeof(cl));
for(reg int i=0;i<m;++i){
read(e[i].x);read(e[i].y);
T[e[i].x].push_back(e[i].y);
T[e[i].y].push_back(e[i].x);
}
for(reg int i=1;i<=n;++i){
sum+=h[i];
if(!~cl[i]) color(i,0);
if(cl[i]) Add(i,n+1,h[i]+Inf);
else Add(0,i,h[i]+Inf);
}
for(reg int i=0;i<m;++i){
if(cl[e[i].x]) Add(e[i].y,e[i].x,INF);
else Add(e[i].x,e[i].y,INF);
}
ll ans=dinic();
printf("%lld %lld\n",n-ans/Inf,sum-ans%Inf);
find(0);
for(int i=1;i<=n;++i) putchar(vis[i]^cl[i]?‘1‘:‘0‘);
fclose(stdin);
fclose(stdout);
return(0);
}