題目描述

NiroBC 是貓咪學(xué)堂一年級(jí)的新生，開(kāi)學(xué)第一天，學(xué)堂組織了一場(chǎng)迎新會(huì)，在
迎新會(huì)上，貓咪們會(huì)互相贈(zèng)送禮物。
一年級(jí)的新生共有 N 只貓咪，編號(hào)為 1 . . . N（包括 NiroBC 自己），其中有
M 對(duì)貓咪是在開(kāi)學(xué)前就互相認(rèn)識(shí)的。學(xué)堂規(guī)定，對(duì)于任意一對(duì)已經(jīng)互相認(rèn)識(shí)的
貓咪 u, v，要么 u 送 v 一份禮物，要么 v 送 u 一份禮物。
學(xué)堂知道貓咪們都十分摳門(mén)，所以希望安排一種送禮物的方案，使得送出禮
物最多的貓咪送出的禮物最少。

輸入格式

第一行兩個(gè)正整數(shù) N, M，表示貓咪的數(shù)量和已經(jīng)互相認(rèn)識(shí)的貓咪的對(duì)數(shù)。
接下來(lái) M 行，每行兩個(gè)整數(shù) u, v，表示 u, v 已經(jīng)互相認(rèn)識(shí)。數(shù)據(jù)保證 u ?= v，
且同一個(gè)數(shù)對(duì)最多出現(xiàn)一次（(u, v) 和 (v, u) 算作同一數(shù)對(duì)）。

輸出格式

一個(gè)整數(shù)，表示送出禮物最多的貓咪最少需要送出幾份禮物。

分析：

由于決策單調(diào)性，所以可以二分答案，而判定mid的合法性可以跑最大流，將個(gè)關(guān)系
當(dāng)作一個(gè)點(diǎn)，源點(diǎn)與這些點(diǎn)相連，容量為1,將這些關(guān)系的點(diǎn)與此關(guān)系的兩個(gè)點(diǎn)連一條
容量為1的邊，最后將這些人的點(diǎn)與匯點(diǎn)連接一條容量為mid的邊，跑出最大流，若等
于關(guān)系數(shù)m，則合法，否則不合法。

代碼：

#include<cstdio> #include<cctype> #define min(a,b) (a<b?a:b) #define out(x) printf("%d",x) #define inf 0x3f3f3f3f #define maxn 1000007 #define maxm 1000007template <typename T> void in(T &x) {char ch=getchar();bool flag=0;while(ch>'9'||ch<'0') flag|=(ch=='-'),ch=getchar();x=ch-'0';ch=getchar();while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();if(flag) x=-x;return ; }int n,m,s,t,cnt=1,cur[maxn],head[maxn],d[maxn],q[maxn]; struct edge{int to,cost,nxt; }e[maxm];void link(int u,int v,int cost){e[++cnt].to=v;e[cnt].nxt=head[u];e[cnt].cost=cost;head[u]=cnt;e[++cnt].to=u;e[cnt].nxt=head[v];e[cnt].cost=0;head[v]=cnt; }bool bfs(){for(int i=0;i<=t;i++)cur[i]=head[i],d[i]=0;int ha=1,ta=1,now;d[s]=1;q[1]=s;while(ha<=ta){now=q[ha++];for(int i=head[now];i;i=e[i].nxt)if(!d[e[i].to]&&e[i].cost){d[e[i].to]=d[now]+1;q[++ta]=e[i].to;if(e[i].to==t) return 1;}}return 0; }int dfs(int u,int flow){if(u==t) return flow;int rest=flow;for(int w,i=cur[u];i;i=e[i].nxt){cur[u]=i;if(e[i].cost&&d[e[i].to]==d[u]+1){w=dfs(e[i].to,min(rest,e[i].cost));if(!w) { d[e[i].to]=0;continue;}e[i].cost-=w;e[i^1].cost+=w;rest-=w;if(rest==0) return flow;}}if(rest==flow)d[u]=0;return flow-rest; }int maxflow=0;void dinic(){int w;maxflow=0;while(bfs())while(w=dfs(s,inf)) maxflow+=w;return ; }void build(){in(n);in(m);s=0,t=n+m+5;for(int i=1,u,v;i<=m;i++){in(u);in(v);link(s,i,1);link(i,u+m,1);link(i,v+m,1);}for(int i=1;i<=n;i++)link(i+m,t,0);return ; }bool work(int x){for(int i=head[s];i;i=e[i].nxt){e[i].cost=1;e[i^1].cost=0;}for(int i=1;i<=m;i++)for(int to,j=head[i];j;j=e[j].nxt){to=e[j].to;if(to!=s){e[j].cost=1;e[j^1].cost=0;}}for(int i=m+1;i<=n+m;i++)for(int to,j=head[i];j;j=e[j].nxt){to=e[j].to;if(to==t){e[j].cost=x;e[j^1].cost=0;}}dinic();if(maxflow==m) return 1;return 0; }int main(){build();int l=1,ans=n,r=n,mid;while(l<=r){mid=(l+r)>>1;if(work(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%d",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ieqefcr/p/9833209.html

總結(jié)

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

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