HDOJ 4687 Boke and Tsukkomi 一般图最大匹配带花树+暴力
and 最大 匹配 暴力 一般 hdoj
2023-09-14 09:08:01 时间
一般图最大匹配带花树+暴力:
先算最大匹配 C1
在枚举每一条边,去掉和这条边两个端点有关的边.....再跑Edmonds得到匹配C2
假设C2+2==C1则这条边再某个最大匹配中
Boke and Tsukkomi
Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)Total Submission(s): 649 Accepted Submission(s): 202
Problem Description
A new season of Touhou M-1 Grand Prix is approaching. Girls in Gensokyo cannot wait for participating it. Before the registration, they have to decide which combination they are going to compete as. Every girl in Gensokyo is both a boke (funny girl) and a tsukkomi
(straight girl). Every candidate combination is made up of two girls, a boke and a tsukkomi. A girl may belong to zero or more candidate combinations, but one can only register as a member of one formal combination. The host of Touhou M-1 Grand Prix hopes
that as many formal combinations as possible can participate in this year. Under these constraints, some candidate combinations are actually redundant as it\'s impossible to register it as a formal one as long as the number of formal combinations has to be
maximized. So they want to figure out these redundant combinations and stop considering about them.
Input
There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers: 1 ≤ N ≤ 40 and 1 ≤ M ≤ 123, where N is the number of girls in Gensokyo, and M is the number of candidate combinations. The following M lines are M candidate combinations, one by each line. Each combination is represented by two integers, the index of the boke girl 1 ≤ Bi ≤ N and the index of the tsukkomi girl 1 ≤ Ti ≤ N, where Bi != Ti.
The first line of each test case contains two integers: 1 ≤ N ≤ 40 and 1 ≤ M ≤ 123, where N is the number of girls in Gensokyo, and M is the number of candidate combinations. The following M lines are M candidate combinations, one by each line. Each combination is represented by two integers, the index of the boke girl 1 ≤ Bi ≤ N and the index of the tsukkomi girl 1 ≤ Ti ≤ N, where Bi != Ti.
Output
For each test case, output the number of redundant combinations in the first line. Then output the space-separated indexes of the redundant combinations in ascending order in the second line.
Sample Input
4 4 1 3 2 3 2 4 3 1 6 6 1 2 3 2 3 4 5 2 5 4 5 6
Sample Output
1 2 3 2 4 5
Author
Zejun Wu (watashi)
Source
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; const int maxn=50; vector<int> ans; bool G[maxn][maxn],TG[maxn][maxn]; int n,m; int Match[maxn]; int Start,Finish,NewBase; int Father[maxn],Base[maxn]; bool InQueue[maxn],InPath[maxn],InBlossom[maxn]; int Count; queue<int> q; int FindCommonAncestor(int u,int v) { memset(InPath,false,sizeof(InPath)); while(true) { u=Base[u]; InPath[u]=true; if(u==Start) break; u=Father[Match[u]]; } while(true) { v=Base[v]; if(InPath[v]) break; v=Father[Match[v]]; } return v; } void ResetTrace(int u) { int v; while(Base[u]!=NewBase) { v=Match[u]; InBlossom[Base[u]]=InBlossom[Base[v]]=true; u=Father[v]; if(Base[u]!=NewBase) Father[u]=v; } } void BlossomContract(int u,int v) { NewBase=FindCommonAncestor(u,v); memset(InBlossom,false,sizeof(InBlossom)); ResetTrace(u); ResetTrace(v); if(Base[u]!=NewBase) Father[u]=v; if(Base[v]!=NewBase) Father[v]=u; for(int tu=1;tu<=n;tu++) { if(InBlossom[Base[tu]]) { Base[tu]=NewBase; if(!InQueue[tu]) { q.push(tu); InQueue[tu]=true; } } } } void FindAugmentingPath() { memset(InQueue,false,sizeof(InQueue)); memset(Father,0,sizeof(Father)); for(int i=1;i<=n;i++) Base[i]=i; while(!q.empty()) q.pop(); q.push(Start); InQueue[Start]=true; Finish=0; while(!q.empty()) { int u=q.front(); q.pop(); InQueue[u]=false; for(int i=1;i<=n;i++) { if(i==u||G[u][i]==false) continue; int v=i; if(Base[u]!=Base[v]&&Match[u]!=v) { if(v==Start||(Match[v]>0&&Father[Match[v]]>0)) BlossomContract(u,v); else if(Father[v]==0) { Father[v]=u; if(Match[v]>0) { q.push(Match[v]); InQueue[Match[v]]=true; } else { Finish=v; return ; } } } } } } void AugmentPath() { int u,v,w; u=Finish; while(u>0) { v=Father[u]; w=Match[v]; Match[v]=u; Match[u]=v; u=w; } } void Edmonds() { memset(Match,0,sizeof(Match)); for(int u=1;u<=n;u++) { if(Match[u]==0) { Start=u; FindAugmentingPath(); if(Finish>0) AugmentPath(); } } } int bian[200][2]; int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(G,0,sizeof(G)); memset(TG,0,sizeof(TG)); ans.clear(); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); bian[i][0]=u;bian[i][1]=v; G[u][v]=G[v][u]=1; TG[u][v]=TG[v][u]=1; } Edmonds(); Count=0; for(int i=1;i<=n;i++) if(Match[i]) Count++; for(int i=0;i<m;i++) { int u=bian[i][0],v=bian[i][1]; ///clear about u,v for(int j=1;j<=n;j++) { G[u][j]=G[j][u]=G[j][v]=G[v][j]=0; } Edmonds(); int C2=0; for(int j=1;j<=n;j++) if(Match[j]) C2++; if(C2<Count-2) ans.push_back(i+1); ///Recover for(int j=1;j<=n;j++) { G[u][j]=TG[u][j]; G[j][u]=TG[j][u]; G[v][j]=TG[v][j]; G[j][v]=TG[j][v]; } } int sz = ans.size(); printf("%d\n",sz); for(int i=0;i<sz;i++) { printf("%d",ans[i]); if(i<sz-1)printf(" "); } printf("\n"); } return 0; }
相关文章
- Little Girl and Maximum XOR(区间最大异或值--技巧)-------------C语言——菜鸟级
- SP Module 5 Speech Synthesis – Phonemes and the Front End
- ORA-26881: ORA-string: string raised in string automatic string job:”string”.”string” for Capture process “string” and cloned Capture process “string”. ORACLE 报错 故障修复 远程处理
- ORA-27136: MPMT and VLM are both enabled ORACLE 报错 故障修复 远程处理
- ORA-01879: the hh25 field must be between 0 and 24 ORACLE 报错 故障修复 远程处理
- ORA-14056: partition number string: sum of PCTUSED and PCTFREE may not exceed 100 ORACLE 报错 故障修复 远程处理
- Oracle详解 GUID and UUID唯一标识符(oracleguid)
- MySQL中的OR与AND操作符比较(mysqlor和and)
- 多条件查询MySQL中使用And多条件查询的步骤(mysql中and)
- 解析:Google开源的“Show and Tell”,是如何让机器“看图说话”的?
- 深入浅出:MySQL中AND和OR运算符使用方法(mysql中and和or)
- Linux ARP Firewall:Protecting Networks and Data(linuxarp防火墙)
- Mastering MySQL: A Guide to Setting Up and Configuring MasterSlave Replication(mysql的主从配置)
- Comparing Oracle Data: Achieving Efficiency and Accuracy(比对数据oracle)
- Exploring the Power and Flexibility of Linux with NM Your Ultimate Guide(nmlinux)
- Oracle中使用除了And的其他查询关键字(oracle中除了and)
- Oracle中使用AND运算符的示例分析(oracle中and用法)