首页 > 代码库 > 【不可能的任务24/200】洛谷1640 bzoj1854游戏 匈牙利就是又短又快
【不可能的任务24/200】洛谷1640 bzoj1854游戏 匈牙利就是又短又快
bzoj炸了，靠离线版题目做了两道（过过样例什么的还是轻松的）但是交不了，正巧洛谷有个“大牛分站”，就转回洛谷做题了
水题先行，一道傻逼匈牙利
其实本来的思路是搜索然后发现写出来类似于匈牙利(⊙o⊙)
（匈牙利的复杂度惊人，1e6秒过）
1 #include <cstdio> 2 bool b[3000001]; 3 int c[3000001],fir[3000001],to[3000001],nex[3000001]; 4 int N,n,p,q; 5 void add(int p,int q) 6 { 7 nex[++N]=fir[p];to[N]=q;fir[p]=N; 8 } 9 bool find(int k)10 {11 b[k]=true;12 for(int i=fir[k];i;i=nex[i])13 if(!c[to[i]]) { c[to[i]]=k;b[k]=false;return true;}14 else 15 if(!b[c[to[i]]] && find(c[to[i]]))16 {17 c[to[i]]=k;b[k]=false;return true;18 }19 b[k]=false;20 return false;21 }22 int main()23 {24 scanf("%d",&n);25 for(int i=1;i<=n;i++)26 {27 scanf("%d%d",&p,&q);28 if(p<=n) add(p,i+n);29 if(q<=n) add(q,i+n);30 }31 for(int i=1;i<=n;i++)32 if(!find(i))33 {34 printf("%d",i-1);35 return 0;36 }37 printf("%d",n);38 return 0;39 }
现在感觉洛谷的界面比bzoj不知道友好到哪里去了
【不可能的任务24/200】洛谷1640 bzoj1854游戏 匈牙利就是又短又快
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。