洛谷1525 关押罪犯

  • 发现题解里面二分图的解法都是(基本上)$bfs$的,所以我就来一发$dfs$的,应该也挺快$(269ms)$,我没有打快读。
  • 至于为什么要二分图我就不解释了,楼上都说的很清楚。二分枚举最大的冲突大小$(Max)$,然后进行二分图染色,如果一条边的权值,小于$Max$,就不鸟它,即把这条边所连接的点暂时保持原来的颜色。因为可能这个点会在后面的$dfs$中被染色。
  • 我主要讲$dfs$的实现,看代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×