文章目錄

• 題目描述
• 解析
• 代碼

網(wǎng)絡(luò)流要大膽建圖

題目描述

公司內(nèi)部共$n$個(gè)員工，員工之間可能有矛盾。若員工$u$和員工$v$有矛盾，用邊$(u,v)$表示，共$m$個(gè)矛盾。

現(xiàn)在公司決定裁員，使得被裁人員間的矛盾指數(shù)最高。矛盾指數(shù)定義為被裁人員間的矛盾總數(shù)與被裁人員數(shù)的比值

解析

感覺(jué)很神仙的題
一開(kāi)始自己的思路是暴力枚舉裁員人數(shù)求最大矛盾，但是如何強(qiáng)制控制裁員人數(shù)把我卡住了…（費(fèi)用流或許能做？）
最后還是看了題解qwq
關(guān)鍵是建圖的方法
把每個(gè)職員和每條矛盾關(guān)系都看作一個(gè)點(diǎn)，那么$(u,v)$可以選取的前提就是$u$和$v$都選取
這樣又成了求最大權(quán)閉合圖的經(jīng)典問(wèn)題

但是如何確定點(diǎn)權(quán)呢？
考慮二分矛盾指數(shù)g，考慮是否存在一種方案，使得：
$$邊數(shù)/點(diǎn)數(shù)>=g$$
移項(xiàng)，得：
$$邊數(shù)?1+點(diǎn)數(shù)?（?g）>=0$$
這樣就可以直接上dinic求了

代碼

#include<bits/stdc++.h> #define ll double using namespace std; const int N=5050; const int M=1e9; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,s,t; struct node{int to,nxt;ll cap; }p[300500]; int fi[N],cnt; void addline(int x,int y,ll cap){p[++cnt]=(node){y,fi[x],cap};fi[x]=cnt;p[++cnt]=(node){x,fi[y],0};fi[y]=cnt; } int col[N],cur[N]; queue<int>q; int bfs(){memset(col,0,sizeof(col));col[s]=1;q.push(s);while(!q.empty()){int now=q.front();q.pop();for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(col[to]||!p[i].cap) continue;col[to]=col[now]+1;q.push(to);}}return col[t]; } ll dfs(int x,ll lim){if(x==t||!lim) return lim;ll res=0;for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap||col[to]!=col[x]+1) continue;ll add=dfs(to,min(lim,p[i].cap));lim-=add;res+=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(lim) col[x]=-1;return res; } ll dinic(){ll res=0;while(bfs()){while(ll tmp=dfs(s,2e15)) res+=tmp;}return res; } int vis[N]; void find1(int x){if(vis[x]) return;vis[x]=1;for(int i=fi[x];~i;i=p[i].nxt){if(!p[i].cap) continue;find1(p[i].to);}return; } void find2(int x){if(vis[x]) return;vis[x]=2;for(int i=fi[x];~i;i=p[i].nxt){if(!p[i^1].cap) continue;find2(p[i].to);}return; } int num; int u[N],v[N]; bool check(double x){memset(fi,-1,sizeof(fi));cnt=-1;double tot=m;s=n+m+1;t=n+m+2;for(int i=1;i<=n;i++){addline(i,t,x);}for(int i=1;i<=m;i++){addline(s,i+n,1);addline(i+n,u[i],2e15);addline(i+n,v[i],2e15);}return tot-dinic()>0; } int main(){n=read();m=read();if(!m){printf("1\n1");return 0;}for(int i=1;i<=m;i++){u[i]=read();v[i]=read();}double st=0,ed=2e9;for(int i=1;i<=100;i++){double mid=(st+ed)/2;if(check(mid)) st=mid;else ed=mid;}check(st);find1(s);int num=0;for(int i=1;i<=n;i++){num+=vis[i]?1:0;}printf("%d\n",num);for(int i=1;i<=n;i++){if(vis[i]) printf("%d\n",i);}return 0; } /* 3 2 1 3 1 2 10 2 3 10 */

總結(jié)

以上是生活随笔為你收集整理的YBTOJ：矛盾指数（网络流-最大权闭合图）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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