停摆??停摆你妹啊!!2011-2012NBA赛季开已经打啦!你OUT了。
有n支队伍比赛,n<=20。已经打了一些比赛,并且知道了A赛区的队伍的目前得分。队伍i的目前得分为score[i],剩余比赛场次为remain[i],剩余场次包括同赛区和异赛区的比赛。用match[i][j]表示A区队伍的剩余的比赛情况,i和j剩余的比赛场数。当然,remain[i]>=sigma{match[i][k],1<=k<=n}。要知道,篮球比赛是没有平局的,问队伍1可不可能在赛季末获得A区的第一名(可以并列第一)?
解:
1. 显然,有种情况是:当队伍1赢下剩下所有比赛,其余队伍输掉剩余比赛,队伍1也不可能赢得第一。
2. 增设源点s和汇点t,两类点:左边点代表队伍,右边点代表某两个队伍之间的比赛。
s到第一类点连边,容量为那支队伍还可以赢得的最多的比赛场数,即(队伍1目前得分+队伍1的剩余比赛场数-队伍i的目前得分);
第二类点到t连边,容量为该点代表的两只队伍剩余的比赛场数K;
第一类点到第二类点:若队伍i和队伍j之间有比赛,且对应的第二类点的标号为p,则连边(i,p,INF),(j,p,INF)。
3. 求最大流。若第二类点到t的边都满流,就可以找到一组解,否则无解。
为何这样建图是对的呢?可以了解到建图的形式为S-->每个队-->比赛-->T,就是把剩余的比赛场数分配到每个队中,每个队的得分不能超过限制。当然这个限制还不够,还需要最小割全部切到与T相连的边上;否则,最小割肯定切到至少两个队伍上的边,而且要打的比赛>0,这样,本来这两个队的得分已经==队伍1的最高得分,再打比赛,肯定会有一个队超过限制,这样队伍1就不肯能获得冠军了。
复杂度分析:点数最多有2+n+(n+1)*n/2<=232,显然用最大流是合适的。听说有更好的方法。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxv = 1000;
const int maxe = 10000;
int n;
int score[30];
int remain[30];
int match[30][30];
//
struct Edge
{
int v;
int next;
int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
void addEdge(int a,int b,int c)
{
e[edgeNum].v = b;
e[edgeNum].flow = c;
e[edgeNum].next = head[a];
head[a] = edgeNum++;
e[edgeNum].v = a;
e[edgeNum].flow = 0;
e[edgeNum].next = head[b];
head[b] = edgeNum++;
}
void Init()
{
edgeNum = 0;
memset(head,-1,sizeof(head));
memset(d,0,sizeof(d));
}
int sap(int s,int t,int n) //源点,汇点,结点总数
{
int i,x,y;
int f,ans = 0;
for(i = 0; i < n; i++)
now[i] = head[i];
vh[0] = n;
x = s;
while(d[s] < n)
{
for(i = now[x]; i != -1; i = e[i].next)
if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
break;
if(i != -1)
{
now[x] = preh[y] = i;
pre[y] = x;
if((x=y) == t)
{
for(f = INF,i=t; i != s; i = pre[i])
if(e[preh[i]].flow < f)
f = e[preh[i]].flow;
ans += f;
do
{
e[preh[x]].flow -= f;
e[preh[x]^1].flow += f;
x = pre[x];
}while(x!=s);
}
}
else
{
if(!--vh[d[x]])
break;
d[x] = n;
for(i=now[x]=head[x]; i != -1; i = e[i].next)
{
if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
{
now[x] = i;
d[x] = d[e[i].v] + 1;
}
}
++vh[d[x]];
if(x != s)
x = pre[x];
}
}
return ans;
}
//
int main()
{
int i,j,k;
int cnt;
while(scanf("%d",&n)!=EOF)
{
Init();
cnt = 0;
for(i = 1; i <= n; i++)
scanf("%d",&score[i]);
for(i = 1; i <= n; i++)
scanf("%d",&remain[i]);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d",&match[i][j]);
int high = score[1] + remain[1];
for(i = 2; i <= n; i++) //剪枝:1队剩下比赛全赢并且其余队全输,仍不能赢得比赛。
{
if(score[i] > high)
break;
}
if(i<=n)
{
printf("NO\n");
continue;
}
for(i = 2; i <= n; i++)
for(j = i+1; j <= n; j++)
if(match[i][j])
cnt++;
int source = 0;
int sink = cnt+n+1;
int flow = 0;
for(i = 2; i <= n; i++)
addEdge(source,i,high-score[i]);
k = 0;
for(i = 2; i <= n; i++)
{
for(j = i+1; j <= n; j++)
{
if(match[i][j])
{
++k;
addEdge(i,n+k,INF);
addEdge(j,n+k,INF);
addEdge(n+k,sink,match[i][j]);
flow += match[i][j];
}
}
}
if(flow == sap(source,sink,sink+1))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
分享到:
相关推荐
SGU推荐题目分类,适合初次使用sgu的编程爱好者使用!
SGU 390 AC源码,数位统计的难题
SGU 385,我写的程序,一道DP题,跟概率有关
SGU题库整合 Volume (200 - 299) pdf版
pku sgu 经典图论题解答, 多种方法解答经典图论题, 附源代码
辛苦整理所得,分略多,绝对值得,sgu完整题库(530个网页,还有试题难度排序)。lnddszp[at]gmail[dot]com
SGU离线题库(2015-6-8整理),图片可以显示。。
sgu oj上的 101-121 的AC代码
SGU-801综合通讯接入装置使用说明书
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
SGU 103AC 代码 质量有保证!
sgu ##这是一个将我的 sol 问题存储到 acm.sgu.ru 的存储库
SGU 333 集训队AC程序,秒过,CPP
SGU题库 Volume (100-199) pdf整合版
987654321问题 4014 肉饼 3998 几乎素数 3845 a ^ b-b ^ a 3673 骨牌 3621 花小店 3417 数数 3290 电话目录 3282 数字根 2874 盒子 2836 276 安德鲁的烦恼 2658 130 圆圈 2555 154 阶乘 2529 114 ...
下载调度程序,用于低带宽环境。 全天扩展下载量
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
HJVXJVHSKVH JHDK JH DFKSDYFS DVJDSVXCVXCVZXCVZXCV
“#babylonjs-sgu”
我的解决方案代码适用于流行的在线裁判系统,例如 POJ、HDOJ、SGU 和 ACM-ICPC Live Archive。 但是,我忘记了我用来解决这些问题的算法! 我将通过竞赛来组织代码和解决方案。 一些索引页面将可用,以便您可以更快...