这应该说是比较神的一个题目了
题意的话,就是有n 个人,两两之间打比赛,每场比赛赢的人加一分,总共呢有n*(n-1)/2个比赛,然后求这样一种人的个数,就是能赢所有比自己分高的人或者他就是分最高的人。 当然我们是求这种人可能的最大个数,
建图的话,就要分两种点,人和比赛,很显然,源点到所有的人建边,容量是该人的得分,所有比赛与汇点建边,容量为1。那么现在要处理的就是人与比赛的关系了。
当我们看到n的大小最多只有10时,就应该意识到这个问题,是否可以枚举呢?
最裸的想法,二进制位枚举strong kings,那么复杂度大概是1000*60 * 60,貌似还不错的样子。
对每个strong kings,设其编号为i,某个比他分高的人为j,那么他俩对应的比赛应该是i赢,那么直接让i去连接这个比赛点就行了,容量为1,代表这是一个必要的边,但是其他的比赛我们不知道结果,就要把比赛双方i,j都连一个容量为1的边到对应的比赛点上。
实验一下,125ms
然后就有了进阶版本的想法了,可以意识到分数越高的人越有可能成为strong kings,然后我们枚举strong kings的个数k,让队列最后k个人成为strong kings。看到网上有人说strong kings'必然是'队列中的后k个人,这句话显然是错的,我们可以通过构造无数不是这样情况的序列, 但是我们可以确定的是,对于一个序列,如果有k个strong kings,那么必然存在一种情况,就是后k个人是strong kings。注意,是‘存在’,而不是‘必然是‘。
现在开始证明 :
假设序列是这个模样,1....i.....j.....k......n
i,k是strong kings,而j不是
假设j输给了j+1至n区间中的x个人,那么显然i是赢了这x个人的,我们现在想把j变为strong kings
那么就让把j输了的这些场全变成赢,此时分值改变了x,就将与i之前的人们的比赛多输x场,这样j的分数守恒了,但是j一赢之后,原本输给的x个人的分数少了,那就让他们都去赢i,这样他们的分数也就守恒了,此时发现i分数又不守恒了,少了x,恰好刚才j去输给i之前的人了x场,i正好去赢x场,这样大家的分数都守恒了。
就这样我们把一个不连续的strong kings们变的紧密了一些,依次这样,直到strong kings都在序列的后面
然后发现,瞬间变成了0ms
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MAXN 75
#define MAXM 5555
#define INF 1000000007
using namespace std;
struct node
{
int ver; // vertex
int cap; // capacity
int flow; // current flow in this arc
int next, rev;
}edge[MAXM];
int dist[MAXN], numbs[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{ //e记录边的总数
edge[e].ver = y;
edge[e].cap = c;
edge[e].flow = 0;
edge[e].rev = e + 1; //反向边在edge中的下标位置
edge[e].next = head[x]; //记录以x为起点的上一条边在edge中的下标位置
head[x] = e++; //以x为起点的边的位置
//反向边
edge[e].ver = x;
edge[e].cap = 0; //反向边的初始容量为0
edge[e].flow = 0;
edge[e].rev = e - 1;
edge[e].next = head[y];
head[y] = e++;
}
void rev_BFS()
{
int Q[MAXN], qhead = 0, qtail = 0;
for(int i = 1; i <= n; ++i)
{
dist[i] = MAXN;
numbs[i] = 0;
}
Q[qtail++] = des;
dist[des] = 0;
numbs[0] = 1;
while(qhead != qtail)
{
int v = Q[qhead++];
for(int i = head[v]; i != -1; i = edge[i].next)
{
if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] < MAXN)continue;
dist[edge[i].ver] = dist[v] + 1;
++numbs[dist[edge[i].ver]];
Q[qtail++] = edge[i].ver;
}
}
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
}
int maxflow()
{
int u, totalflow = 0;
int Curhead[MAXN], revpath[MAXN];
for(int i = 1; i <= n; ++i)Curhead[i] = head[i];
u = src;
while(dist[src] < n)
{
if(u == des) // find an augmenting path
{
int augflow = INF;
for(int i = src; i != des; i = edge[Curhead[i]].ver)
augflow = min(augflow, edge[Curhead[i]].cap);
for(int i = src; i != des; i = edge[Curhead[i]].ver)
{
edge[Curhead[i]].cap -= augflow;
edge[edge[Curhead[i]].rev].cap += augflow;
edge[Curhead[i]].flow += augflow;
edge[edge[Curhead[i]].rev].flow -= augflow;
}
totalflow += augflow;
u = src;
}
int i;
for(i = Curhead[u]; i != -1; i = edge[i].next)
if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
Curhead[u] = i;
revpath[edge[i].ver] = edge[i].rev;
u = edge[i].ver;
}
else // no admissible arc, then relabel this vertex
{
if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!
Curhead[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != src)
u = edge[revpath[u]].ver; // Backtrack
}
}
return totalflow;
}
int id[22][22];
int score[22];
int fg[22][22];
int nt, num;
void cut(char *s)
{
int len = strlen(s);
int t = 0;
for(int i = 0; i < len; i++)
{
if(s[i] >= '0' && s[i] <= '9')
{
t = t * 10 + s[i] - '0';
if(i == len - 1 || s[i + 1] == ' ')
{
score[++nt] = t;
t = 0;
}
}
}
}
void build(int k)
{
init();
for(int i = 1; i <= nt; i++) add(src, i, score[i]);
for(int i = nt + 1; i <= num; i++) add(i, des, 1);
memset(fg, 0, sizeof(fg));
for(int i = nt - k + 1; i <= nt; i++)
for(int j = i + 1; j <= nt; j++)
if(score[i] < score[j])
add(i, id[i][j], 1), fg[i][j] = 1;
for(int i = 1; i <= nt; i++)
for(int j = i + 1; j <= nt; j++)
if(!fg[i][j])
add(i, id[i][j], 1), add(j, id[i][j], 1);
}
int main()
{
int T;
char s[555];
scanf("%d", &T);
getchar();
while(T--)
{
gets(s);
nt = 0;
cut(s);
num = nt;
for(int i = 1; i <= nt; i++)
for(int j = i + 1; j <= nt; j++)
id[i][j] = id[j][i] = ++num;
src = num + 1;
des = num + 2;
n = des;
int ans = -1;
for(int i = nt; i >= 1; i--)
{
build(i);
rev_BFS();
if(maxflow() == nt * (nt - 1) / 2)
{
ans = i;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
该题记录了本人研究该题的记录,有些是心得,希望能给大家帮助。
poj2516代码最小费用最大流
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
西北工业大学POJ试题C++答案代码+课程设计
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
北大POJ1159-Palindrome 解题报告+AC代码
poj openjudge 1111题最大正向匹配 提交ac
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
POJ1837-Balance 解题报告+AC代码