[洛谷P1640] [SCOI2010]连续攻击游戏

题目链接：

传送门点我

题目分析：

一道建图很巧妙的二分图。把每个装备的两个属性分别连边到它的编号上，这样原问题就转化成了在二分图上找增广路的过程。因为题目要求使用装备的属性的编号连续，所以找增广路时如果找不到则直接break出来即可。
因为数据很大，所以需要加时间戳优化。

代码：

#include<bits/stdc++.h>
#define N 1000000*4+5
using namespace std;
inline int read(){
    int cnt=0,f=1;char c;
    c=getchar();
    while(!isdigit(c)){
        if(c==‘-‘)f=-f;
        c=getchar();
    }
    while(isdigit(c)){
        cnt=cnt*10+c-‘0‘;
        c=getchar();
    }
    return cnt*f;
}

int n,tot=0,idx=0,ans=0,res,x,y,nxt[N],first[N],to[N],match[N];
int vis[N];

void add(int x,int y){
    nxt[++tot]=first[x];
    first[x]=tot;
    to[tot]=y;
}

int find(int u){
    for(register int i=first[u];i;i=nxt[i]) {
        int v=to[i];
//      cout<<v<<endl;
        if(vis[v]==idx) continue;
        else {
            vis[v]=idx;
            if(match[v]==-1||find(match[v])){
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int hungary(){
    for(register int i=1;i<=n+1;i++) match[i]=-1;
    for(register int i=1;i<=10000;i++){
        ++idx;
        if(!find(i)) break;
        else ans++;
//      cout<<idx<<" ";
    }
    return ans;
}

int main(){
    n=read();
    for(register int i=1;i<=n;i++){
        x=read();y=read();
        add(x,i);add(y,i);
    }
    res=hungary();
    printf("%d",res);
    return 0;
}

[洛谷P1640] [SCOI2010]连续攻击游戏

原文：https://www.cnblogs.com/kma093/p/10327254.html