第九届省赛 -- 二分答案+二分图匹配

题意：
给定一个n*n矩阵，矩阵内值非零表示该处有怪物且怪物的经验值为矩阵内值。每一行每一列至多消灭一个怪物，现要求消灭最大的怪物，并在这个前提下求出能获得的最大经验值。你所获得的经验值为你所消灭的所有怪物的经验值中最小的那个。

分析：
二分图最大匹配+二分。
对于所有矩阵内值非零a[i][j]，从X部的i点向Y部的j点连一条边。对此二分图求出最大匹配ans。那么ans为最多能消灭的怪物数量。然后二分枚举经验值k，对于所有矩阵内值a[i][j]>=k的，按照上面一样重新建图并求出最大匹配sum。如果sum等于ans，那么经验值k是合法的。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 509;
const int MAXM = 250009;
int tu[MAXN][MAXN];
struct edge{
    int to,next;
}edge[MAXM];
int head[MAXM],tot;
void init()
{
    tot = 0;
    memset(head,-1,sizeof head);
}
int ANS;
void addedge(int u,int  v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int linker[MAXN];
bool used[MAXN];
int uN,n;
bool dfs(int u)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v = edge[i].to;
        if(!used[v])
        {
            used[v] = true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v] = u;
                return 1;
            }
        }
    }
    return false;
}
int hungry()
{
    int res =0 ;
    memset(linker,-1,sizeof linker);
    for(int u=1;u<=uN;u++)
    {
        memset(used,0,sizeof used);
        if(dfs(u))res++;
    }
    return res;
}
bool check(int k)
{
    init();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(tu[i][j]>=k)
            {
                addedge(i,j);
            }
        }
    }
    return hungry()==ANS;
}
int main()
{

        cin>>n;
        uN = n;
        init();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&tu[i][j]);
                if(tu[i][j]>0)
                addedge(i,j);
            }
        }
        ANS = hungry();
        int l =0 ,r = 1e9;
        while(l<r)
        {
            int mid = (l+r+1)>>1;
            if(check(mid))
            {
                l = mid;
            }
            else r = mid-1;
        }
        printf("%d\n",l);

}

#include<cstdio>
#include<algorithm>
using namespace std;
struct s{
    int va, x, y;
};
s arr[505*505];
bool cmp(s a,s b){
    if(a.va!=b.va)return a.va < b.va;
    if(a.x!=b.x)return a.x < b.x;
    return a.y < b.y;
}
int main(){
    int N, len;
    int dir_c[505] = {0}, dir_r[505] = {0};
    scanf("%d",&N);
    len = N * N;
    for(int i=1;i<=N;i++){
        dir_c[i] = dir_r[i] = N;
        for(int j=1;j<=N;j++){
            scanf("%d",&arr[(i-1)*N+j].va);
            arr[(i-1)*N+j].x = i;
            arr[(i-1)*N+j].y = j;
            //dir_c[i]++,dir_r[j]++;
        }
    }

    sort(arr+1,arr+1+len,cmp);
    for(int i=1;i<=len;i++){
        if(arr[i].va && (dir_c[arr[i].x]<=1||dir_r[arr[i].y]<=1)){
            printf("%d\n",arr[i].va);
            break;
        }
        dir_c[arr[i].x]--,dir_r[arr[i].y]--;
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct data {
    int ai, x, y;
}a[510 * 510];
bool cmp(data x, data y) {
    if(x.ai != y.ai) return x.ai < y.ai;
    else if(x.x != y.x) return x.x < y.x;
    return x.y < y.y;
}
int d_c[510], d_r[510];
int main() {
    int n, i, j, len;
    scanf("%d", &n);
    len = n * n;
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j) {
            scanf("%d", &a[(i - 1) * n + j].ai);
            a[(i - 1) * n + j].x = i;
            a[(i - 1) * n + j].y = j;
            d_c[i] ++, d_r[j] ++;
        }
    sort(a + 1, a + 1 + len, cmp);
    for(i = 1; i <= len; ++ i) {
        if(a[i].ai != 0 && (d_c[a[i].x] <= 1 || d_r[a[i].y] <= 1)) {
            printf("%d\n", a[i].ai);
            break ;
        }
        d_c[a[i].x] --, d_r[a[i].y] --;
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505,M=(N*N+2*N)*2,inf=2e9;
int n,S,T,tt,tot,h[N*2],to[M],nx[M],c[M],l[N*2],q[N*2];
struct edg{
    int v,a,b;
    void in(int _a,int _b,int _c){
        a=_a,b=_b,v=_c;
    }
    bool operator<(const edg &r)const{
        return v<r.v;
    }
}e[N*N];
void add(int u,int v){
    to[++tt]=v,nx[tt]=h[u],h[u]=tt,c[tt]=1;
    to[++tt]=u,nx[tt]=h[v],h[v]=tt,c[tt]=0;
}
inline bool bfs(){
    memset(l,0,T+1<<2);
    int f,r;
    l[q[f=r=1]=S]=1;
    while(f<=r){
        int x=q[f++];
        for(int i=h[x];i;i=nx[i])
            if(c[i]>0&&!l[to[i]])  
                l[q[++r]=to[i]]=l[x]+1;
    }return l[T]>0;
}
inline int dfs(int p,int C) {
    if(p==T||!C) return C;
    int r=C,t;
    for(int i=h[p];i;i=nx[i])
        if(c[i]&&l[to[i]]==l[p]+1){
            t=dfs(to[i],min(c[i],r));
            r-=t,c[i]-=t,c[i^1]+=t;
            if(!r) break;
        }
    if(r==C) l[p]=0;
    return C-r;
}
int flow(int u){
    tt=1;for(int i=S;i<=T;++i) h[i]=0;
    for(int i=tot;i&&e[i].v>=u;--i)
        add(e[i].a,e[i].b+n);
    for(int i=1;i<=n;++i)
        add(S,i),add(i+n,T);
    int ret=0;
    while(bfs()) ret+=dfs(S,inf);
    return ret;
}
int main(){
    scanf("%d",&n);T=2*n+1;
    for(int i=1;i<=n;++i)
        for(int j=1,a;j<=n;++j){
            scanf("%d",&a);
            if(a) e[++tot].in(i,j,a);
        }
    sort(e+1,e+tot+1);
    int uu=flow(0),l=1,r=e[tot].v;
    while(l<r){
        int mid=l+r+1>>1;
        if(flow(mid)<uu) r=mid-1;
        else l=mid;
    }
    printf("%d",l);
    return 0;
}

vector版（参考）：

#include <bits/stdc++.h>
using namespace std;
const int maxn=550;
int n;
int from[maxn],w[maxn][maxn],ans,vis[maxn];
vector<int> g[maxn];
void init()
{
    for(int i=0;i<n;i++) g[i].clear();
}
bool Find(int u)
{
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!vis[v])
        {
            vis[v]=1;
            if(from[v]==-1 || Find(from[v]))
            {
                from[v]=u;
                return true;
            }
        }
    }
    return false;
}
int match()
{
    int ret=0;
    memset(from,-1,sizeof(from));
    for(int i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Find(i)) ret++;
    }
    return ret;
}
bool check(int k)
{
    init();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(w[i][j]>=k)
            g[i].push_back(j);
    return match()==ans;
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            scanf("%d",&w[i][j]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
        {
            if(w[i][j])
            {
                g[i].push_back(j);
            }
        }
        ans=match();
        int L=0,R=1e9;
        while(L<R)
        {
            int mid=(L+R+1)>>1;
            if(check(mid))
                L=mid;
            else
                R=mid-1;
        }
        printf("%d\n",L);
    }
    return 0;
}