| 比赛 |
| 难度级别：D； 运行时间限制：2000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
初三年级举办了一场篮球赛，共有N个班级参加。当WZJ知道了这件事情， 已经打完了若干场比赛（WZJ一直在写Fenwich套Treap），接下来还要进行M场比赛。第i场比赛的竞争班级是ai,bi，胜者得2分，负者得0 分，若平局则两班各得1分。为了让得分尽量平均，现在给出每个班级已经得到的分数si，与接下来M场比赛的安排，请你回答得分最多的班级的得分最少是多 少。
|
|
输入
|
|
第一行为两个正整数N，M。
第二行为N个正整数si。 接下来M行每行两个正整数ai,bi。 |
|
输出
|
|
请你回答得分最多的班级的得分最少是多少。
|
|
输入示例
|
|
5 3
1 2 2 1 3 1 5 2 3 4 5 |
|
输出示例
|
|
3
|
|
其他说明
|
|
第一场比赛1赢
第二场比赛平局 第三场比赛4赢 则最后每个班级的得分都是3 1<=N<=1000 1<=M<=50000 1<=si<=100 1<=ai!=bi<=M |
题解：赤裸裸的网络流建模。
首先看到破题口"得分最多的班级的得分最少是多少"先二分答案，将问题转化为"得分为point的方案是否可行"。怎么检查可行呢？（或者说怎么样才算可行）就是强制分配这么多的得分，如果每一场比赛都成功分配了两个队的分数我们就称之为"可行"（其实算是ISAP的处理流的办法：我们先模拟大量的流，不断地修正检查获得结果。以前我都不知道= =）。当然了，这么想是很辨证的，事实上一定会有其他的解法。
继续，我们怎么分配分数并检查呢？仔细阅读这道题的特殊性：每场比赛一定会贡献两个积分，于是我们就用流来模拟积分的流动转移，最后在汇点处用容量卡每个队能获取分数的最大值。易知当且仅当每场比赛都分配出了两个积分（即最大流是比赛数量的两倍时）这样的方案是合法的。
Ps二分图还是跑Dinic吧，ISAP快不了多少：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
struct ISAP{
struct tedge{int x,y,w,next;}adj[maxm];int ms,fch[maxn];
int d[maxn],s[maxn],cur[maxn],gap[maxn],n,top;
void init(int n){
this->n=n;ms=;top=;
memset(d,-,sizeof(d));
memset(fch,-,sizeof(fch));
return;
}
void addedge(int u,int v,int w){
adj[ms]=(tedge){u,v,w,fch[u]};fch[u]=ms++;
adj[ms]=(tedge){v,u,,fch[v]};fch[v]=ms++;
return;
}
void bfs(){
queue<int>Q;Q.push(n);d[n]=;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=fch[u];i!=-;i=adj[i].next){
int v=adj[i].y;
if(d[v]==-) d[v]=d[u]+,Q.push(v);
}
} return;
}
int maxflow(int S,int T){
n=T;bfs();int k=S,i,flow=;
for(i=;i<=n;i++) cur[i]=fch[i],gap[d[i]]++;
while(d[S]<n){
if(k==n){
int mi=inf,pos;
for(i=;i<top;i++) if(adj[s[i]].w<mi) mi=adj[s[i]].w,pos=i;
for(i=;i<top;i++) adj[s[i]].w-=mi,adj[s[i]^].w+=mi;
flow+=mi;top=pos;k=adj[s[top]].x;
}
for(i=cur[k];i!=-;i=adj[i].next){
int v=adj[i].y;
if(adj[i].w&&d[k]==d[v]+){cur[k]=i;k=v;s[top++]=i;break;}
}
if(i==-){
int lim=n;
for(i=fch[k];i!=-;i=adj[i].next){
int v=adj[i].y;
if(adj[i].w&&d[v]<lim) lim=d[v],cur[k]=i;
} if(--gap[d[k]]==) break;
d[k]=lim+;gap[d[k]]++;
if(k!=S) k=adj[s[--top]].x;
}
} return flow;
}
}sol;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
int n,m,a[maxn],b[maxn],p[maxn];
bool check(int point){
sol.init(n+m+);
int S=n+m+,T=n+m+;
for(int i=;i<=m;i++){
sol.addedge(S,i,);
sol.addedge(i,a[i]+m,inf);
sol.addedge(i,b[i]+m,inf);
}
for(int i=;i<=n;i++) sol.addedge(i+m,T,point-p[i]);
return sol.maxflow(S,T)==m<<;
}
void init(){
int L=,R=;n=read();m=read();
for(int i=;i<=n;i++) p[i]=read(),L=max(L,p[i]);
for(int i=;i<=m;i++) a[i]=read(),b[i]=read();
R=L+(m<<);
while(L<R){
int M=L+R>>;
if(check(M)) R=M;
else L=M+;
}
write(L);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}
搜索
复制