首页 > 代码库 > 【二分图】【并查集】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem L. Canonical duel
【二分图】【并查集】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem L. Canonical duel
给你一个网格(n<=2000，m<=2000)，有一些炸弹，你可以选择一个空的位置，再放一个炸弹并将其引爆，一个炸弹爆炸后，其所在行和列的所有炸弹都会爆炸，连锁反应。
问你所能引爆的最多炸弹数。
转化成：
将行列当成点，炸弹当成边，然后你可以给这个二分图加1条边，问你最大的连通块的边的数量。
可以通过枚举所有可以建的边，通过并查集来尝试更新答案。由于一条边必然会让总度数+2，所以一个连通块的边数是所有点的度数之和/2。
并查集不必要动态维护集合的大小，一开始就建好并查集，提前统计好即可。
最后枚举的时候不会再在并查集之间再连边了，只会直接去更新答案。
队友的代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int Ans,num[6000],a[2003][2003],fa[6000],ans[6000],n,m,ansx,ansy;
char ch;
int get(int x) {
return fa[x]==x?x:fa[x]=get(fa[x]);
}
void un(int x,int y)
{
int X=get(x),Y=get(y);
if(X!=Y) fa[X]=Y;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
while(ch=getchar(),ch!=‘+‘&&ch!=‘.‘);
a[i][j]=ch;
if(ch==‘+‘)
{
num[i]++;
num[j+n]++;
}
}
}
Ans=0;
for(int i=1;i<=n+m;++i)
{
fa[i]=i;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
if(a[i][j]==‘+‘)
{
un(i,j+n);
}
}
for(int i=1;i<=n+m;++i)
{
ans[get(i)]+=num[i];
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
if(a[i][j]==‘.‘)
{
int nowans=ans[get(i)];
if(get(i)!=get(j+n))
{
nowans+=ans[get(j+n)];
}
if(nowans/2>Ans)
{
Ans=nowans/2;
ansx=i;
ansy=j;
}
}
}
printf("%d\n",Ans);
if(Ans)
{
printf("%d %d\n",ansx,ansy);
}
return 0;
}
【二分图】【并查集】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem L. Canonical duel
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。