首页 > 代码库 > uvalive 3231 Fair Share 公平分配问题 二分+最大流 右边最多流量的结点流量尽量少。
uvalive 3231 Fair Share 公平分配问题 二分+最大流 右边最多流量的结点流量尽量少。
/** 题目: uvalive 3231 Fair Share 公平分配问题 链接:https://vjudge.net/problem/UVALive-3231 题意:有m个任务,n个处理器,每个任务有两个候选处理器,只要其中一个运行,该任务就能执行。 不同任务的两个候选处理器,至少有一个不同。 求任务数最多的那个处理器所分配的任务数尽量少。 思路:二分+最大流 左边是任务,s->u,cap = 1。 如果任务u和u的候选处理器v,u->v, cap = 1. 右边是处理器,二分mi。所有处理器v,v->t, cap = mi; 求s-t最大流flow,如果flow等于任务数,那么可行解。找一个最小的mi即可。 */ #include<iostream> #include<cstring> #include<vector> #include<map> #include<cstdio> #include<sstream> #include<algorithm> #include<queue> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; typedef long long LL; const int N = 11010;///n+m=1000+10000=11000; struct Edge{ int from, to, cap, flow; Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }; struct Dinic{ int n, m, s, t; vector<Edge> edges; vector<int> G[N]; bool vis[N]; int d[N]; int cur[N]; void init(int n) { this->n = n; for(int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS(){ memset(vis, 0, sizeof vis); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++){ Edge &e = edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow){ vis[e.to] = 1; d[e.to] = d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a){ if(x==t||a==0) return a; int flow = 0, f; for(int &i = cur[x]; i < G[x].size(); i++){ Edge& e = edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){ e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a==0) break; } } return flow; } int Maxflow(int s,int t){ this->s = s, this->t = t; int flow = 0; while(BFS()){ memset(cur, 0, sizeof cur); flow += DFS(s,INF); } return flow; } }; int main() { int T, n, m; cin>>T; while(T--) { scanf("%d%d",&n,&m); int s = 0, t = n+m+1; Dinic dinic, save; dinic.init(t); int u , v; for(int i = 1; i <= m; i++){ scanf("%d%d",&u,&v); dinic.AddEdge(s,i,1); dinic.AddEdge(i,u+m,1); dinic.AddEdge(i,v+m,1); } save = dinic; int lo = 0, hi = INF, mi, ans; while(lo<=hi){ mi = (lo+hi)/2; dinic = save; for(int i = 1; i <= n; i++){ dinic.AddEdge(i+m,t,mi); } int flow = dinic.Maxflow(s,t); if(flow==m){ ans = mi; hi = mi-1; }else { lo = mi+1; } } printf("%d\n",ans); } return 0; }
uvalive 3231 Fair Share 公平分配问题 二分+最大流 右边最多流量的结点流量尽量少。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。