二分图的时间戳优化+并查集变型

P1640 [SCOI2010]连续攻击游戏

用used数组记录now(now++),不需要每一轮都是用memset判别。

#include 

using namespace std;
const int maxn=4e6+5;
int n,link[maxn],ans,cnt,now,head[maxn];
int used[maxn];
struct node
{
    int to,nxt;
}e[maxn];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int dfs(int u)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(used[v]!=now)
        {
            used[v]=now;
            if(link[v]==-1||dfs(link[v]))
            {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
void hungary()
{
    memset(link,-1,sizeof(link));
    for(int i=1;i>n;
    for(int i=1;i>u>>v;
        add(u,i);add(v,i);
    }
    hungary();
    cout