題目+評測傳送門

思路

其實這一題有2種不同的思路,但是由于我實在是太蒟蒻了,只會其中一種,另一種看了半天都不知道它在講什么/(ㄒoㄒ)/~~

首先,我們要學習一下二分圖及其判斷方法博客,然后這個題目就很好解決了,我們二分計算仇恨值,然后在如果2人仇恨值大于mid,我們就把他們相連,然后判斷這個圖是否是二分圖,即在左右部分里面"沒有沖突",而判斷是否是二分圖的方法,上面給的鏈接里面也講了,然后這道題就OK啦

代碼

1 #include<bits/stdc++.h> 2 #define FOR(i,a,b) for(register int i=a;i<=b;i++) 3 #define ll long long 4 #define gc getchar(); 5 using namespace std; 6 int n,m,maxx=0,num=0,ans; 7 int head[20000+10]; 8 int colo[20000+10]; 9 struct s1 10 { 11 int fm,to,vl,nt; 12 }a[2*100000+10]; 13 int scan() 14 { 15 int as=0,f=1;char c=gc; 16 while(c>'9'||c<'0'){if(c=='-') f=-1;c=gc}; 17 while(c>='0'&&c<='9') {as=(as<<3)+(as<<1)+c-'0';c=gc}; 18 return as*f; 19 } 20 void ad(int fm,int to,int vl) 21 { 22 a[++num].nt=head[fm]; 23 a[num].fm=fm;a[num].to=to;a[num].vl=vl; 24 head[fm]=num; 25 } 26 bool chek(int mid) 27 { 28 memset(colo,0,sizeof(colo)); 29 queue <int> q; 30 FOR(i,1,n) 31 { 32 if(colo[i]) continue; 33 q.push(i);colo[i]=1;//如果沒有進入,隨便進入一個坑,反正之前的都 34 //已經解決完了 35 while(!q.empty()) 36 { 37 int u=q.front(); q.pop(); 38 for(int j=head[u];j;j=a[j].nt) 39 { 40 if(a[j].vl>=mid) 41 { 42 if(colo[a[j].to]==0) 43 { 44 colo[a[j].to]=colo[u]==1?2:1;//對立面的顏色 45 q.push(a[j].to); 46 } 47 else if(colo[a[j].to]==colo[u]) return false; 48 } 49 } 50 } 51 } 52 return true; 53 } 54 int main() 55 { 56 n=scan();m=scan(); 57 FOR(i,1,m) 58 { 59 int f,t,v; 60 f=scan();t=scan();v=scan(); 61 maxx=max(v,maxx); 62 ad(f,t,v);ad(t,f,v); 63 } 64 int l=0,r=maxx+1; 65 while(l+1<r) 66 { 67 int mid=(l+r)>>1; 68 if(chek(mid)) r=mid; 69 else l=mid; 70 } 71 cout<<l; 72 return 0; 73 }

?

轉載于:https://www.cnblogs.com/KSTT/p/10368510.html

總結

以上是生活随笔為你收集整理的关押罪犯洛谷P1525的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。