手机网站制作明细报价表,电商网站功能,表白网站制作器,艺术字体在线设计免费版题目描述 NiroBC 是猫咪学堂一年级的新生#xff0c;开学第一天#xff0c;学堂组织了一场迎新会#xff0c;在 迎新会上#xff0c;猫咪们会互相赠送礼物。 一年级的新生共有 N 只猫咪#xff0c;编号为 1 . . . N#xff08;包括 NiroBC 自己#xff09;#xff0c;其… 题目描述 NiroBC 是猫咪学堂一年级的新生开学第一天学堂组织了一场迎新会在 迎新会上猫咪们会互相赠送礼物。 一年级的新生共有 N 只猫咪编号为 1 . . . N包括 NiroBC 自己其中有 M 对猫咪是在开学前就互相认识的。学堂规定对于任意一对已经互相认识的 猫咪 u, v要么 u 送 v 一份礼物要么 v 送 u 一份礼物。 学堂知道猫咪们都十分抠门所以希望安排一种送礼物的方案使得送出礼 物最多的猫咪送出的礼物最少。 输入格式 第一行两个正整数 N, M表示猫咪的数量和已经互相认识的猫咪的对数。 接下来 M 行每行两个整数 u, v表示 u, v 已经互相认识。数据保证 u ̸ v 且同一个数对最多出现一次(u, v) 和 (v, u) 算作同一数对。 输出格式 一个整数表示送出礼物最多的猫咪最少需要送出几份礼物。 分析 由于决策单调性所以可以二分答案而判定mid的合法性可以跑最大流将个关系 当作一个点源点与这些点相连容量为1,将这些关系的点与此关系的两个点连一条 容量为1的边最后将这些人的点与汇点连接一条容量为mid的边跑出最大流若等 于关系数m则合法否则不合法。 代码 #includecstdio
#includecctype
#define min(a,b) (ab?a:b)
#define out(x) printf(%d,x)
#define inf 0x3f3f3f3f
#define maxn 1000007
#define maxm 1000007template typename T void in(T x) {char chgetchar();bool flag0;while(ch9||ch0) flag|(ch-),chgetchar();xch-0;chgetchar();while(ch0ch9) x(x3)(x1)ch-0,chgetchar();if(flag) x-x;return ;
}int n,m,s,t,cnt1,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].tov;e[cnt].nxthead[u];e[cnt].costcost;head[u]cnt;e[cnt].tou;e[cnt].nxthead[v];e[cnt].cost0;head[v]cnt;
}bool bfs(){for(int i0;it;i)cur[i]head[i],d[i]0;int ha1,ta1,now;d[s]1;q[1]s;while(hata){nowq[ha];for(int ihead[now];i;ie[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].tot) return 1;}}return 0;
}int dfs(int u,int flow){if(ut) return flow;int restflow;for(int w,icur[u];i;ie[i].nxt){cur[u]i;if(e[i].costd[e[i].to]d[u]1){wdfs(e[i].to,min(rest,e[i].cost));if(!w) { d[e[i].to]0;continue;}e[i].cost-w;e[i^1].costw;rest-w;if(rest0) return flow;}}if(restflow)d[u]0;return flow-rest;
}int maxflow0;void dinic(){int w;maxflow0;while(bfs())while(wdfs(s,inf)) maxfloww;return ;
}void build(){in(n);in(m);s0,tnm5;for(int i1,u,v;im;i){in(u);in(v);link(s,i,1);link(i,um,1);link(i,vm,1);}for(int i1;in;i)link(im,t,0);return ;
}bool work(int x){for(int ihead[s];i;ie[i].nxt){e[i].cost1;e[i^1].cost0;}for(int i1;im;i)for(int to,jhead[i];j;je[j].nxt){toe[j].to;if(to!s){e[j].cost1;e[j^1].cost0;}}for(int im1;inm;i)for(int to,jhead[i];j;je[j].nxt){toe[j].to;if(tot){e[j].costx;e[j^1].cost0;}}dinic();if(maxflowm) return 1;return 0;
}int main(){build();int l1,ansn,rn,mid;while(lr){mid(lr)1;if(work(mid)) ansmid,rmid-1;else lmid1;}printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/ieqefcr/p/9833209.html
