注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1305][CQOI2009]dance跳舞  

2014-11-19 16:14:36|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1305: [CQOI2009]dance跳舞

不太会做,到网上看到三种版本题解,只有一种是对的
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
const int MAX = 2E9+7;
const int N = 50+10;
const int P = N*4;
const int M = P*P*2;
int n,m,T,start,end,large;
int du[P],level[P];
struct Point{
Point(){next = NULL;}
int d;Point *next;
void push(int);
}point[P],*cur[P];
queue<Point*>pupa;
Point *newPoint(){
if(pupa.empty())return new Point;
Point *r = pupa.front();pupa.pop();
if(r->next)pupa.push(r->next);
*r=Point();return r;
}
void Point::push(int a){
Point *l = new Point;
l->next = next;next = l;
l->d =a;
}
struct Edge{
int from,to,cap,flow;
Edge(){}
Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl){}
}edges[M];
queue<int>dui;
bool bfs(){
for(int i=1;i<=large;i++)level[i]=0;
level[start] = 1;dui.push(start);
while(!dui.empty()){
int now = dui.front();dui.pop();
for(Point *i = point[now].next;i!=NULL;i=i->next){
Edge e = edges[i->d];
if(!level[e.to] && e.cap > e.flow){
level[e.to] = level[now] + 1;
dui.push(e.to);
}
}
}
return level[end]!=0;
}
int dfs(int now,int a){
if(now == end||!a)return a;
int flow=0,l;
for(Point *&i = cur[now];i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(level[now]+1==level[e.to] && (l=dfs(e.to,min(e.cap-e.flow,a)))>0){
flow += l;
a -= l;
e.flow += l;
edges[i->d^1].flow -= l;
if(!a)break;
}
}return flow;
}
void AddEdge(int from,int to,int cap){
point[from].push(T);
edges[T++]=Edge(from,to,cap,0);
point[to].push(T);
edges[T++]=Edge(to,from,0,0);
}
int dinic(){
int flow =0 ;
while(bfs()){
int flag;
for(int i=1;i<=large;i++)cur[i] = point[i].next;
while((flag = dfs(start,MAX)))
flow += flag;
}return flow;
}
short map[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
bool check(int mid){
int i,j;
T=0;
for(i=1;i<=large;i++)
if(point[i].next)pupa.push(point[i].next),point[i].next=NULL;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(map[i][j])AddEdge(i,j+n,1);
else AddEdge(i+2*n,j+3*n,1);
for(i=1;i<=n;i++){
AddEdge(start,i,mid);
AddEdge(i,i+2*n,m);
AddEdge(i+3*n,i+n,m);
AddEdge(i+n,end,mid);
}
i = dinic();
return i == n*mid;
}
int main(){
int i,j;char cc;
n = scan();m = scan();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf(" %c",&cc);
if(cc=='Y') map[i][j] = 1;
}
start = 4*n+1;large = end = start+1;
int l=0,r=n;
while(l < r){
int mid=(l+r+1)/2;
if(check(mid))l = mid;
else r = mid-1;
}
printf("%d\n",l);
return 0;
}

题解:
二分答案+网络流check
二分一个答案mid,然后S向每个男生i连一条边mid,每个女生j连一条边mid到T。
如果两个人ij互相喜欢就连一条容量为1的边,如果不喜欢就把i'->j'连一条容量为1的边。
最后连i->i' j->j'容量均为t
对于网上的其它两种做法:
第一种是直接贪心统计,第二种是建图之后跑一遍网络流在残余网络里贪心统计。
第一种显然错就不说了
第二种错误的地方有两个问题,第一个是把喜欢和不喜欢混为一谈了,第二个是这种做法可能会导致某一个人和很多人匹配。
有一个很明显的样例可以hack掉第二种方法:

4 2
YYYN
YYNY
YNNY
NYNY

正确答案是0,而错误结果是1
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017