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

 
 
 

日志

 
 

JSOI 2009 Day2 游戏 ( BZOJ 1443 ) 判断一个点是否必在二分图最大匹配上  

2014-02-02 00:04:18|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
-------------------------------------------------------------------------------------------
废话部分
当初选择做这个题 只是因为自己好久没写
二分图最大匹配和网络流的题了
本想快速复习下的
结果居然是误入深坑。。。
Day1
 当看到此题PV为二分图最大匹配时
(不过看PV的行为已经被众神犇吐槽过一次了)
我想到一个问题
这所有的点都是一个集合中的 如何进行匹配呢
(BZOJ才做30多题 就不要因为我想到这个问题而惊讶了)
于是先问了问某蒟蒻 然后某蒟蒻告诉我是“带花树”,然后就不理我了
然后又问了Foreseeable带花树 Foreseeable说带花树编写麻烦
不过就在这个瞬间机智的我想到了染色法 
于是问题就正式地转化为了二分图最大匹配
-------------------------------------------------------------------------------------------
主要部分
开始进行二分图最大匹配了
结果样例都没过 什么情况?
原来这题不是裸的二分图最大匹配啊
于是再想了想 发现此题的主要问题是——见标题
然后就想到了删点来判断 
枚举要删的点 然后每次做一次匹配来判断是否为最大匹配必经点
可是这样就是N次匈牙利算法了
然后就是O(NE+N^2*E)=O(N^2*E)了显然会TLE
忽然发现某亲切的学长上线了 就问了问他
然后他也说是枚举删点
不过从删点后导致的失配的那个点开始做一次增广
(怎么让我忽然想到了ISAP的当前弧优化?
不过我的逻辑是乱的 所以就不要问我这两个有什么关系了)
这样的话就变为N次增广
然后就是O(NE+NE)=O(NE)了 上界4*10^8
 由于BZOJ是总实现 所以数据较大的点用1s+是绝对可以的
再加上C++在BZOJ上的种族天赋——by dwjshift
所以我决定就是它了
由于很晚了 然后脑子一直很晕
白白怒送不少WA

Day2
忽然发现昨天写的真心无逻辑
改了改后自己试的几组样例都A了 但还是WA
又找了ydc ydc还没做过这题
于是继续听他的对拍
对拍出错误的数据范围较小的数据后——
(附赠神奇的样例 至少我在这个数据上WA了不少次)
6 6
.#.###
####..
##.###
.#..#.
#..#.#
#..##.
——居然继续犯傻 怀疑学长的方法不好实现
自己yy了一种方法
/***************************************************************************
错误思想 仅供参考(不过改进下其实也就是后面的正解)
我们称做完一次匈牙利算法后没有在一起的点为自由点
然后对于可以与自由点在一起的点 可以与它们在一起的点也都是自由点
然后就是通过现有的自由点无限递推的过程
***************************************************************************/
又为此送掉了几个WA  
还是相信学长的方法吧 于是又回到了之前的那个问题
然后我的思路忽然清晰了 就如同能30ms写完一篇作文的感觉 
(一般我都要1.5h的)
然后就是改正后的“错误”思想
/***************************************************************************
我们称做完一次匈牙利算法后没有在一起的点为自由点
然后对于可以与自由点在一起的点 当前与它们在一起的点是自由点
然后就是通过现有的自由点无限递推的过程—(可以直接沿着这条线去看证明)—*
***************************************************************************/                               |
不过最后实现还是先用了学长的增广的方法                                                                    |
不过只是判断能否增广 真的重新增广的话实现会复杂些                                               |
毕竟这又改变了原图啦                                                                                                        |
(真的半夜真的好晕 连用的是那种方法都分不清了)                                                   |
大概就是这样了                                                                                                                    |
然后交了后发现ydc在几个小时前就A掉了。。。                                                           |
第一次提交要8000+ms 总时限才10000ms                                                                     |
感觉绝对是方法还不够好吧 目测一大堆没用匈牙利                                                      |
而直接用最大流的都可以比这快很多                                                                               |
所以 明天再改改看吧                                                                                                         |
                                                                                                                                              |
Day3                                                                                                                                      |
-------------------------------------------------------------------------------------------                              |
早上起床时 精神还是好些                                                                                                  |
对于我yy出的自由点的方法                                                                                              | 
其实如果证明了一个性质                                                                                                 |
就只用在求出最大匹配后一次全图的dfs                                                                         |
这样就是O(NE+(N+E))=O(NE)                                                                         |
但是匈牙利的NE是极端数据的情况下 所以明显会小很多                                           | 
/***************************************************************************                            |
性质证明                                                                                                        <  ———— *
对于任意一个自由点 能与它在一起的点绝对不是自由点
因为如果两个自由点能在一起
显然还没有达到最大匹配
***************************************************************************/
在BZOJ上第二次交 只用了200ms左右233


/*************更新(某同学问了我证明部分 然后我大概想了想 差不多就是这样)
 我们假设A一直按最大匹配去走(现在走到了点X) 那么A输掉的情况就是 B走到了一个点(Y) 而这个点已经没有了没有被匹配过的但是却是可以匹配的点那么起点一定可以不在最大匹配上 因为X可以与Y匹配 然后一直这样匹配回去
********************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=10010,E=40010;
int color[N];
int firste[N],nexte[E],v[E];
int dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0};
int used[N],pos[N],aim[N];
int n,m,e=0,node,ans;
int gain=0,dian=0;
void build_edge(int x,int y)
{
++e;
nexte[e]=firste[x];
firste[x]=e;
v[e]=y;
++e;
nexte[e]=firste[y];
firste[y]=e;
v[e]=x;
}
int dfs(int u)
{
if(u==-1)return 0;
for(int p=firste[u];p;p=nexte[p])
if(!used[v[p]])
{
used[v[p]]=1;
if(!aim[v[p]]||dfs(aim[v[p]]))
{
aim[v[p]]=u;
pos[u]=v[p];
return 1;
}
}
return 0;
}
int dfsa(int u)
{
used[u]=2;
for(int p=firste[u];p;p=nexte[p])
if(!used[v[p]])
{
used[v[p]]=1;
if(!used[pos[v[p]]])
dfsa(pos[v[p]]);
}
}
int dfsp(int u)
{
used[u]=2;
for(int p=firste[u];p;p=nexte[p])
if(!used[v[p]])
{
used[v[p]]=1;
if(!used[aim[v[p]]])
dfsp(aim[v[p]]);
}
}
int ys(int x,int y)
{
return (x-1)*m+y;
}
int main()
{
char ch;
scanf("%d%d",&n,&m);
rep(i,n)
rep(j,m)
{
ch=getchar();
while(ch!='.'&&ch!='#')
ch=getchar();
if(ch=='.')
{
++dian;
if((i+j)&1)color[ys(i,j)]=1;
else color[ys(i,j)]=2;
}
}
rep(i,n)
rep(j,m)
{
int tmp=ys(i,j);
if(color[tmp]==2)
rep(k,4)
{
int t1=i+dx[k],t2=j+dy[k];
if(t1>=1&&t1<=n&&t2>=1&&t2<=m)
if(color[ys(t1,t2)])
build_edge(tmp,ys(t1,t2));
}
}
node=n*m;
rep(i,node)
if(color[i]==2)
{
memset(used,0,sizeof(used));
if(dfs(i))
++gain;
}
if(gain*2==dian)
{
printf("LOSE\n");
return 0;
}
printf("WIN\n");
memset(used,0,sizeof(used));
rep(i,node)
if(color[i]&&!used[i]&&!pos[i]&&!aim[i])
{
if(color[i]==1)dfsa(i);
else dfsp(i);
}
int x,y;
rep(i,node)
if(used[i]==2)
{
x=(i-1)/m+1;
y=i-(x-1)*m;
printf("%d %d\n",x,y);
}
return 0;
}


  评论这张
 
阅读(206)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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