简要の题意

求二分图 最大权 最大独立集 的方案。

\(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);
}