GMOJ 6683. 我图呢 题解

简要の题意

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

\(n\le 500\)

思路

二分图最大权独立集很好做，二分图最大独立集也很好做。

考虑 双关键字排序 中第一个关键字无穷大于第二个关键字的优先级。

所以可以令点的数量带来的流量远大于权值带来的流量。

\(+\infty\) 即可。

构造方案直接按求割做。

CODE

#include
#include
#include
#include
#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 T[N];
bool vis[N];
struct edge{
    int x,y;
}e[N*N];
char BuF[FSIZE],*InF=BuF;
templatevoid 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::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