首页 > 代码库 > POJ 2699 The Maximum Number of Strong Kings （最大流+枚举）
POJ 2699 The Maximum Number of Strong Kings （最大流+枚举）
http://poj.org/problem?id=2699
题意：
一场联赛可以表示成一个完全图，点表示参赛选手，任意两点u, v之间有且仅有一条有向边(u, v)或( v, u)，表示u打败v或v打败u。一个选手的得分等于被他打败的选手总数。一个选手被称为“strong king”当且仅当他打败了所有比他分高的选手。分数最高的选手也是strong king。现在给出某场联赛所有选手的得分序列，由低到高，问合理安排每场比赛的结果后最多能有几个strong king。已知选手总数不超过10个。
思路：
选手总数很少，我们可以考虑枚举。
枚举当前strong king的个数为num个，那么可能存在分数最高的num个人是strong king，其余情况也可能存在，但这种情况是最可能的，只要满足这个就可以了。
建立源点和汇点，源点和每场比赛相连（比赛共有n*（n-1）/2场），容量为1，汇点和选手相连，容量为选手分数。
那么比赛和选手怎么连接呢？
如果选手i是strong king，那么凡是分数比他高的人，他都必须要赢，此时把这场比赛和i相连。
如果i和j都不是strong king，那么这场比赛无所谓谁输谁赢，将这场比赛和i和j都连起来就可以。
最后跑最大流，如果等于n*（n-1）/2，就是可以的。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 using namespace std; 12 typedef long long LL; 13 typedef pair<int,int> pll; 14 const int INF=0x3f3f3f3f; 15 const int maxn=300+5; 16 17 int n; 18 int score[maxn]; 19 int com[maxn][maxn]; 20 21 struct Edge 22 { 23 int from,to,cap,flow; 24 Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){} 25 }; 26 27 struct Dinic 28 { 29 int n,m,s,t; 30 vector<Edge> edges; 31 vector<int> G[maxn]; 32 bool vis[maxn]; 33 int cur[maxn]; 34 int d[maxn]; 35 36 void init(int n) 37 { 38 this->n=n; 39 for(int i=0;i<n;++i) G[i].clear(); 40 edges.clear(); 41 } 42 43 void AddEdge(int from,int to,int cap) 44 { 45 edges.push_back( Edge(from,to,cap,0) ); 46 edges.push_back( Edge(to,from,0,0) ); 47 m=edges.size(); 48 G[from].push_back(m-2); 49 G[to].push_back(m-1); 50 } 51 52 bool BFS() 53 { 54 queue<int> Q; 55 memset(vis,0,sizeof(vis)); 56 vis[s]=true; 57 d[s]=0; 58 Q.push(s); 59 while(!Q.empty()) 60 { 61 int x=Q.front(); Q.pop(); 62 for(int i=0;i<G[x].size();++i) 63 { 64 Edge& e=edges[G[x][i]]; 65 if(!vis[e.to] && e.cap>e.flow) 66 { 67 vis[e.to]=true; 68 d[e.to]=d[x]+1; 69 Q.push(e.to); 70 } 71 } 72 } 73 return vis[t]; 74 } 75 76 int DFS(int x,int a) 77 { 78 if(x==t || a==0) return a; 79 int flow=0, f; 80 for(int &i=cur[x];i<G[x].size();++i) 81 { 82 Edge &e=edges[G[x][i]]; 83 if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0) 84 { 85 e.flow +=f; 86 edges[G[x][i]^1].flow -=f; 87 flow +=f; 88 a -=f; 89 if(a==0) break; 90 } 91 } 92 return flow; 93 } 94 95 int Maxflow(int s,int t) 96 { 97 this->s=s; this->t=t; 98 int flow=0; 99 while(BFS())100 {101 memset(cur,0,sizeof(cur));102 flow +=DFS(s,INF);103 }104 return flow;105 }106 }DC;107 108 int solve(int num,int cnt)109 {110 int tot=n*(n-1)/2;111 int src=http://www.mamicode.com/0,dst=n+tot+1;112 DC.init(dst+1);113 114 for(int i=1;i<=n;i++)115 DC.AddEdge(i,dst,score[i]);116 for(int j=n+1;j<=cnt;j++)117 DC.AddEdge(src,j,1);118 119 for(int i=1;i<=n;i++)120 for(int j=i+1;j<=n;j++)121 {122 if(score[i]>score[j] && j>n-num) DC.AddEdge(com[i][j],j,1);123 else if(score[i]<score[j] && i>n-num) DC.AddEdge(com[i][j],i,1);124 else125 {126 DC.AddEdge(com[i][j],i,1);127 DC.AddEdge(com[i][j],j,1);128 }129 }130 return DC.Maxflow(src,dst)==tot;131 }132 133 int main()134 {135 //freopen("D:\\input.txt","r",stdin);136 int T;137 scanf("%d",&T);138 getchar();139 while(T--)140 {141 n=0;142 string str;143 getline(cin,str);144 stringstream ss(str);145 int x;146 while(ss>>x) score[++n]=x;147 148 int num=n;149 for(int i=1;i<=n;i++)150 for(int j=i+1;j<=n;j++)151 com[i][j]=com[j][i]=++num;152 153 154 for(int i=n;i>=0;i--)155 {156 if(solve(i,num)) {printf("%d\n",i);break;}157 }158 }159 return 0;160 }
POJ 2699 The Maximum Number of Strong Kings （最大流+枚举）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。