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

题目链接

https://www.luogu.org/problem/P1640

题解

建模非常巧妙的一道题。

对于编号为 \(i\) 的装备，设其属性分别为 \(a,b\)，我们分别从 \(a,b\) 向 \(i\) 点连边。

接下来我们从 \(1\) 号点按顺序跑匈牙利算法，这个过程就相当于给每一轮（即每个属性）找对应的匹配武器，如果能找到，表明可以进行一次攻击，否则游戏结束。

（刚开始的实现代码极其不优雅，常数巨大…）

#include <cstdio>
#include <cstring>
struct edge
{
 int v,next;
}e[2000005];
int head[10005],res[1000005],cnt;
bool vis[1000005];
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool dfs(int u)
{
 for(int i=head[u];i;i=e[i].next)
 {
  int v=e[i].v;
  if(!vis[v])
  {
   vis[v]=1;
   if(!res[v]||dfs(res[v]))
   {
    res[v]=u;
    return true;
   }
  }
 }
 return false;
}
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  addedge(x,i);
  addedge(y,i);
 }
 for(int i=1;i<=10000;i++)
 {
  memset(vis,0,sizeof(vis));
  if(!dfs(i))
  {
   printf("%d\n",i-1);
   return 0;
  }
 }
 puts("10000");
 return 0;
}