目录
显示
题目链接
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; }