题解 P1525 【关押罪犯】

- 发现题解里面二分图的解法~~都是~~（基本上）$bfs$的，所以我就来一发$dfs$的，应该也挺快$(269ms)$，我没有打快读。 - 至于为什么要二分图我就不解释了，楼上都说的很清楚。二分枚举最大的冲突大小$(Max)$，然后进行二分图染色，如果一条边的权值，小于$Max$，就不鸟它，即把这条边所连接的点暂时保持原来的颜色。因为可能这个点会在后面的$dfs$中被染色。 - 我主要讲$dfs$的实现，看代码： ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; struct edge{ int v,w,next; }Edge[200005]; int n,m,col[20005],data[200005];//这是一个非常坑的地方，因为是无向图 int head[20005],cnt;//要建两条有向边，所以总边要乘2！ int l,r,mid,Max; bool book[20005]; inline void AddEdge(int u,int v,int w){//邻接链表存边 cnt++; Edge[cnt].v=v; Edge[cnt].w=w; Edge[cnt].next=head[u]; head[u]=cnt; return; } bool dfs(int u,int color){//基本上二分图染色都可以参照这个模板 if (book[u]) return col[u]==color;//如果访问过，那么看看染得色会不会冲突 book[u]=true; col[u]=color; bool flag=true; for (int i=head[u];i!=0&&flag;i=Edge[i].next){ int v=Edge[i].v; if (Edge[i].w<=Max) continue;//如果比枚举的最大边Max小，可以不用管它，即把它暂时 flag=dfs(v,1-color);//放在原来的联通块中 } return flag; } inline bool Colored(){ memset(book,false,sizeof (book));//不要忘了初始化 memset(col,0,sizeof (col)); Max=data[mid]; for (int i=1;i<=n;i++){ if (book[i]) continue; if (!dfs(i,0)) return false;//如果冲突直接退出 } return true; } int main(){ int u,v,w; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); data[i]=w; AddEdge(u,v,w); AddEdge(v,u,w); } sort (data+1,data+m+1);//我这里是从边的大小二分，所以要排序 l=0; r=m; while (l<r){ mid=(l+r)>>1; if (Colored()) r=mid;//二分中的r=mid还是r=mid+1等问题一定要想清楚！ else l=mid+1; } printf ("%d\n",data[l]); return 0; } ``` - 最后打个广告：[$MyBlog$](https://www.17shou.vip/)，逃~~