CODEVS 1069

題意 給你n個(gè)人 m條關(guān)系

每個(gè)關(guān)系代表如果 這兩個(gè)人在一個(gè)監(jiān)獄 那么會(huì)產(chǎn)生一個(gè)v的貢獻(xiàn) 監(jiān)獄長(zhǎng)會(huì)看見(jiàn)最大的貢獻(xiàn) 問(wèn)你如何使得分配監(jiān)獄貢獻(xiàn)最小

我們這樣來(lái)想 貢獻(xiàn)具有單調(diào)性 如果mid 滿(mǎn)足 那么mid + 1 肯定也是滿(mǎn)足的 所以我們首先二分

然后二分的時(shí)候比這個(gè)值大的我們要建一條邊 代表放兩個(gè)監(jiān)獄 然后加完邊的無(wú)向圖跑一個(gè)二分圖判別即可判斷這個(gè)情況是否合法?

合法就 使得 r = mid - 1 否則 l = mid + 1

/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq */ #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <map> #include <stack> #include <set> #include <sstream> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl #define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl #define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll; typedef long long ll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const ll INF = 0x3f3f3f3f3f3f3f3f; const ll _INF = 0xc0c0c0c0c0c0c0c0; const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;} ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);} const int MAX_N = 20025; const int MAX_M = 100025; vector<int > G[MAX_N]; struct node {int a,b,c; }arr[MAX_M]; int col[MAX_N],n,m; bool flag; void dfs(int x,int v) {col[x] = v;int sz = G[x].size();for(int i = 0;i<sz;++i){int to =G[x][i];if(!col[to]){dfs(to,3-v);}else if(col[to]==col[x]){flag = false;break;}} } bool check(int mid) {flag = true;vector<int > M[MAX_N];swap(G,M);for(int i = 1;i<=m;++i){if(arr[i].c>mid){G[arr[i].a].push_back(arr[i].b);G[arr[i].b].push_back(arr[i].a);}}memset(col,0,sizeof(int)*(n+1));for(int i = 1;i<=n;++i) if(!col[i]&&flag) dfs(i,1);if(flag) return true;return false; } int main() {//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);scanf("%d%d",&n,&m);for(int i = 1;i<=m;++i){scanf("%d%d%d",&arr[i].a,&arr[i].b,&arr[i].c);}int l = 0,r = inf;while(l<=r){int mid = (l+r)>>1;if(check(mid)) r = mid - 1;else l = mid + 1;}printf("%d\n",l);//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CODEVS 1069 关押罪犯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。