P1525关押罪犯题解

不同的人有不同的做法，看见题解里一群并查集，说实在并查集做法我是不会的。我的做法是老师随口提到到，二分+判断是否构成二分图 首先我们二分枚举最大的影响力（由于是求最小的最大，满足二分的性质，很容易想到二分），那么很显然，影响力大于我们所枚举的midd的罪犯就必须拆开，那么现在我们为他们之间连出一条边。每条边都连上之后，我们得到了几个连通图（注意是几个，不是只有一个），下面我们要对这些连通图判断它们能否拆成两边，这就是所谓的判断二分图。 只要会二分图判定，这题就已经解决的吧 下面我来介绍一下二分图判定的方法（我只介绍一种，染色法） 首先我们枚举每一个点，如果这个点没有染色，那么我们开始我们的算法。首先把这个点标记成黑色，然后开始bfs，枚举所有与它相连的点，将它们标记成白色（在我的程序里用1和2表示颜色），不断遍历整张图，如果你发现下一个染色的点已经有了颜色，判断是否与此时你在的点颜色一致。若是颜色一致，说明染色存在冲突，无法拆成二分图，直接return false。如果无误，直到队列为空退出（注意只有没染色的点才需要加入队列）。之后我们枚举下一个点，若已染色则跳过，没有的话说明我们找到了一张新的图，接下来我们只需要重复上面的步骤就行了。 很好理解的染色法吧 除了这个我想还有一点需要注意，关于二分时如何改变midd。这样想，如果当前的midd值足够让我拆成二分图，那么我就继续把它再变小（二分的贪心性质嘛），然后就。。。。这题就能A了，知道了原理，不难吧，代码实现也很容易。 下面我附上代码： ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=100000+15; int n,m,sum; int head[maxn]; struct node{int to;int z;int next;}edge[maxn*2]; inline int read() { char ch; int fu=1,x=0; for (ch=getchar(); ch<=32; ch=getchar()); if (ch=='-') fu=-1,ch=getchar(); for (x=0; ch>32; ch=getchar()) x=x*10+ch-48; return x*fu; } void add(int x,int y,int z) { edge[++sum].next=head[x]; edge[sum].to=y; edge[sum].z=z; head[x]=sum; } bool bfs(int midd) { int color[maxn]; memset(color,0,sizeof(color)); queue <int> q; for (int j=1;j<=n;j++) { if (color[j]) continue; q.push(j);color[j]=1; do { int k=q.front();q.pop(); for (int i=head[k];i;i=edge[i].next) if (edge[i].z>=midd) { if (color[edge[i].to]==0) { color[edge[i].to]=color[k]==1?2:1; q.push(edge[i].to); } else if (color[edge[i].to]==color[k]) return false; } }while (!q.empty()); } return true; } int main() { int maxx; n=read();m=read(); for (int i=1;i<=m;i++) { int a,b,c; a=read();b=read();c=read(); maxx=max(maxx,c); add(a,b,c); add(b,a,c); } int l=0,r=maxx+1,midd; while (l+1<r) { midd=(l+r)>>1; if (bfs(midd)) r=midd; else l=midd; } printf("%d",l); return 0; } ```