[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注