首页 > 代码库 > 【POJ2699】The Maximum Number of Strong Kings 枚举(二分)+网络流check、
【POJ2699】The Maximum Number of Strong Kings 枚举(二分)+网络流check、
题意:
有n个人,两两都有比赛,然后有每个人的胜场次数。
规定把比自己胜场次数多的人都赢了的就是strong(weak) king (vegetables)
(why i say that they are so weak?
:****,how do you think a person who beat the heroes but defeated at the dogface? )
让你安排比赛,问最多有多少个strongking?
题解:
首先(有人说)能证如果有k个sk,那么一定可以是rating最高的那k个。
然后枚举k,水图check验证maxflow。
破题水。
代码:
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 405 // 网络图中点 #define G 100000 // 网络图中边 #define P 15 // 原图中点等 #define M 50 // 原图中边等 #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3fll #define LL int using namespace std; struct KSD { int v,next,len; }e[G]; int head[N],cnt; void add(int u,int v,int len) { cnt++; e[cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } queue<int>q; int d[N],s,t; bool bfs() { memset(d,0,sizeof(d)); int i,u,v; while(!q.empty())q.pop(); q.push(s),d[s]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i;i=e[i].next)if(e[i].len) { v=e[i].v; if(!d[v]) { d[v]=d[u]+1; if(v==t) return 1; q.push(v); } } } return 0; } int dinic(int x,int flow) { if(x==t)return flow; int remain=flow,k; int i,v; for(i=head[x];i&&remain;i=e[i].next) { v=e[i].v; if(e[i].len&&d[v]==d[x]+1) { k=dinic(v,min(remain,e[i].len)); if(!k)d[v]=0; e[i^1].len+=k,e[i].len-=k; remain-=k; } } return flow-remain; } int n,m,maxflow; int rating[P]; bool cmp(int a,int b){return b<a;} void build(int mid) { int i,j,cnt=n; for(i=1;i<=n;i++)add(s,i,rating[i]),add(i,s,0); for(j=1;j<=n;j++)for(i=j+1;i<=n;i++) { cnt++; add(i,cnt,1),add(cnt,i,0); if(i>mid||rating[j]==rating[i])add(j,cnt,1),add(cnt,j,0); add(cnt,t,1),add(t,cnt,0); } } void work() { int i; char inp[5]; n=0; while(scanf("%c",&inp[0])!=EOF&&inp[0]!='\n')if(inp[0]!=' ')rating[++n]=inp[0]-'0'; m=n*(n-1)/2; s=n+m+1,t=n+m+2; sort(rating+1,rating+n+1,cmp); for(i=n;i;i--) // 枚举sk个数,n<=10,二分见鬼去吧~~ { cnt=1; memset(head,0,sizeof(head)); build(i); maxflow=0; while(bfs())maxflow+=dinic(s,inf); if(maxflow==m) { printf("%d\n",i); return ; } } return ; } int main() { freopen("test.in","r",stdin); int g;for(scanf("%d",&g),getchar();g--;)work(); }读(dou)者(bi)们RE的是不是没删freopen?
【POJ2699】The Maximum Number of Strong Kings 枚举(二分)+网络流check、
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。