每日一题

题意：

二分图的建图：

每件装备只能用一次，如果把攻击序列建成点，就是装备和攻击顺序的匹配。

比如属性值是3和5，那么这件装备要么在3位置要么在5位置被使用。

当然，按攻击顺序开始匹配，一旦匹配不成功，根据题意就必须中止。

还有，每次memset太慢了，用时间戳id。(或者bitset也行)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
vector<int>G[maxn];
int dfn[maxn],matched[maxn],n,m,e;
int head[maxn],cnt=0;
struct node
{
    int to,next;
}edge[2*maxn];
void add(int u,int v)
{
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    head[u]=cnt;
}
int dfs(int u,int t)
{
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dfn[v]!=t)
        {
            dfn[v]=t;
            if(!matched[v]||dfs(matched[v],t))
            {
                matched[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int maxmatch()
{
    int ans=0;
    //memset(matched,0,sizeof matched);
    for(int i=1; i<=10001; i++)
    {
        if(dfs(i,i))
            ans++;
        else
            break;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,i);
        add(v,i);
    }
    printf("%d\n",maxmatch());
}