[Luogu 1640] SCOI2010 连续攻击游戏

DP太恶心，回来二分图这边放松一下心智。

这个建图真的是难以想到。

因为要递增啊，属性值放x部，装备放y部，对应连边跑Hungary就好了。

注意如果中间有点匹配不到了就要直接停止，输出答案（因为无法做到连续递增了）。

就这样。颓废产物。

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN=1010010,MAXM=2000010;bool vis[MAXN];int n,m,cnt,ans,head[MAXN],match[MAXN];struct edge{    int nxt,to;}e[MAXM];void AddEdge(int u,int v){    e[++cnt].nxt=head[u];    e[cnt].to=v;    head[u]=cnt;}void AddEdges(int x,int y,int v){    AddEdge(x,v),AddEdge(y,v);}int max3(int a,int b,int c){    return max(max(a,b),c);}bool DFS(int u){    for(int i=head[u],v;i;i=e[i].nxt)        if(!vis[v=e[i].to])        {            vis[v]=1;            if(!match[v] || DFS(match[v]))            {                match[u]=v,match[v]=u;                return 1;            }        }    return 0;}void Hungary(void){    for(int i=1;i<=m;++i)        if(!match[i])        {            memset(vis,0,sizeof vis);            if(DFS(i))                ++ans;            else                break;        }    printf("%d\n",ans);}int main(int argc,char *argv[]){    scanf("%d",&n);    for(int i=1,x,y;i<=n;++i)    {        scanf("%d %d",&x,&y);        AddEdges(x,y,i+10000);        m=max3(m,x,y);    }    Hungary();    return 0;}