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

ydc的博客

 
 
 

日志

 
 

CTSC 2008 bzoj 1143 祭祀  

2014-01-24 17:56:58|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题的传统做法是二分图匹配
《组合数学》上有经典定理,最小链覆盖数 = 最长反链长度最长链长度 = 最小反链覆盖数
vfleaking写过详细的证明
http://vfleaking.blog.163.com/blog/static/1748076342012918105514527/

这样做的做法,点数是O(n)的,边数是O(n^2)的,再跑匈牙利算法,复杂度是O(n^3)的
今天考了加强版,点数和边数是5*10^4和1.5*10^5
当点数变大为5*10^4级别时,这个方法不仅TLE而且直接就MLE了

这道题第一眼看上去容易想到一个错误的做法,那就是跑最小路径覆盖
但是很容易发现这是错的
然后我们发现,这是一个路径可以相交的最小路径覆盖问题
回顾最小路径覆盖问题做法:
每个点拆成两个点,若(a,b)有边,则让a的左侧点向b的右侧点连边,n-最大匹配数为最小路径覆盖
二分图题目都能转化为网络流题目,于是有做法:S向a右侧连边,a右侧向a左侧连边,a左侧向T连边。然后若a,b有边,a左侧向b右侧连边。容量均为1
这样能做到路径不相交
我们修改建图方式
a向b连边的容量为+oo,a的右侧向a左侧连边也为+oo
如此一来,就能满足可以相交了
答案为n-最大流,时间复杂度为maxflow(n,m),由于网络流的复杂度远远小于理论复杂度以及图的特殊性(边权不是1就是+oo),无疑是优秀的算法

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define maxm 1000010
using namespace std;
int n,m;
int S,T,N;
int dis[maxn],gap[maxn];
int nEdge=1,to[maxm],next[maxm],remain[maxm],start[maxn];
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void make(int a,int b,int c)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],remain[nEdge]=c,start[a]=nEdge;
++nEdge,to[nEdge]=a,next[nEdge]=start[b],remain[nEdge]=0,start[b]=nEdge;
}
void read()
{
Read(n),Read(m);
N=2*n,S=++N,T=++N;
for(int i=1;i<=n;++i)
make(S,i,1),make(i+n,T,1),make(i+n,i,1<<30);
for(int i=1,a,b;i<=m;++i)
{
Read(a),Read(b);
make(a,b+n,1<<30);
}
}
void BFS(int p)
{
static int queue[maxn];
for(int i=1;i<=N;++i)
dis[i]=-1,gap[i]=0;
int front=0,rear=1;
queue[rear]=p,dis[p]=0,gap[0]=1;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(dis[to[i]]==-1)
{
queue[++rear]=to[i];
++gap[dis[to[i]]=dis[p]+1];
}
}
}
void Prepare(int *a,int *b)
{
for(int i=1;i<=N;++i)
a[i]=b[i];
}
int Sap(int p,int flow,int *start)
{
if(p==T)
return flow;
int ans=0;
for(int &i=start[p];i;i=next[i])
if(dis[p]==dis[to[i]]+1&&remain[i])
{
int t=Sap(to[i],min(flow-ans,remain[i]),start);
remain[i]-=t,remain[i^1]+=t,ans+=t;
if(ans==flow)
return ans;
}
if(--gap[dis[p]]==0)
dis[S]=N;
if(dis[S]==N)
return ans;
++gap[++dis[p]];
return ans;
}
int MaxFlow()
{
static int tmp[maxn];
int ans=0;
for(BFS(T);dis[S]<N;Prepare(tmp,start),ans+=Sap(S,1<<30,tmp));
return ans;
}
int main()
{
freopen("skill.in","r",stdin);
freopen("skill.out","w",stdout);
read();
printf("%d\n",n-MaxFlow());
fclose(stdin);
fclose(stdout);
return 0;
}


  评论这张
 
阅读(556)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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