比赛的时候没时间去看，赛后也是看了题解才过的。
题目的意思是，给定二分图，判断哪些边是无用的，也就是一定不会在最大匹配中出现。
解题思路：
我们可以先跑一边匹配，因为点比较多，只能用HK来做。
得到一个最大匹配后，枚举每条边，判断其是否为无用边。
可以分情况考虑：
设u,v为边的两端点。
一、match[u]==v （即 match[v]==u）表示这条边为当前最大匹配的一条边，那肯定是可以用边。如果不是，则转到(2)。
二、因为match[u]!=v （即 match[v]!=u ）那么，可以分一下情况考虑：
（1）match[u]==-1，也就是u尚未匹配，那么此时让u去匹配v，也一定不会导致最大匹配变小，所以该边为有用边。
（2）match[v]==-1，思路同上。
（3）match[u]!=-1 && match[v]!=-1 那么，如果让u匹配v，则会让match[u]和match[v]失去匹配对象，那么我们将得到一个匹配，失去两个匹配。此时，我们分析，只要:
1.match[v]到match[u]之间存在一条增广路，使match[v]匹配match[u]。
2.存在某个点x（与u同为X部）,match[x]==-1,能够找到一条增广路到达match[u]，使得x匹配match[u]。
3.存在某个点y(与v同为Y部)，match[y]==-1,从match[v]出发，能够找到一条增广路到达y，使得match[v]匹配y。
那么就可以补偿我们失去的一个匹配。
解法：
当然，每次枚举边去搜一次增广路的复杂度是很高的，我们可以通过预处理得到解。
将原来的边转化,若ui匹配vi，则连边vi->ui，若ui不匹配vi，则ui->vi。
这样，我们可以通过求强连通分量来判断条件1是否成立。
bfs预处理出所有match[x]==-1的点能够到达的点判断条件2是否成立。
将边反转一次，bfs预处理出match[y]==-1的点能够到达的点，判断条件3是否成立。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define For(i,forN) for(int i=0;i<(forN);i++) #define Rep(i,forN) for(int i=(forN);i>=0;i--) #define ForEdge(i,u) for(int i=head[u];i!=-1;i=edge[i].next) #define sf scanf #define pf printf #define mp make_pair #define _clr(x,y) memset(x,y,sizeof(x)) const int Maxn=101000,Maxe=Maxn*10; int match[Maxn],dis[Maxn],head[Maxn],etot,X,Y; int n,m; struct Edge { int to,next; }edge[Maxe]; void init_edge() { etot=0; _clr(head,-1); } void add_edge(int u,int v) { edge[etot].to=v; edge[etot].next=head[u]; head[u]=etot++; } bool bfs() { bool res=false; queue < int > q; For(i,n) if(match[i]==-1) q.push(i); _clr(dis,0); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!dis[v]) { dis[v]=dis[u]+1; if(match[v]==-1) res=true; else { dis[match[v]]=dis[v]+1; q.push(match[v]); } } } } return res; } bool find(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dis[v]==dis[u]+1) { dis[v]=0; if(match[v]==-1 || find(match[v])) { match[v]=u; match[u]=v; return true; } } } return false; } int HK() { int res=0; _clr(match,-1); while(bfs()) { For(i,n) if(match[i]==-1 && find(i)) res++; } return res; } int E[Maxe][2]; bool Res[Maxe],vis[Maxn],nice[Maxn],canReach[2][Maxn]; int bleg[Maxn],stk[Maxn],dfsn[Maxn],low[Maxn],vtime,scc,top; void tarjanDfs(int u) { vis[u]=true; stk[top++]=u; dfsn[u]=low[u]=vtime++; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!vis[v]) { tarjanDfs(v); low[u]=min(low[u],low[v]); } else if(bleg[v]==-1) low[u]=min(low[u],dfsn[v]); } if(dfsn[u]==low[u]) { do { bleg[stk[--top]]=scc; }while(stk[top]!=u); scc++; } } void Tarjan() { _clr(vis,false); _clr(bleg,-1); vtime=top=0; For(i,n) if(!vis[i]) tarjanDfs(i); } void Visit(int ind) { _clr(vis,false); _clr(canReach[ind],false); queue < int > q; if(ind==0) { For(i,X) if(match[i]==-1) q.push(i),vis[i]=true,canReach[ind][i]=true; } else { for(int i=X;i<n;i++) if(match[i]==-1) q.push(i),vis[i]=true,canReach[ind][i]=true; } while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; canReach[ind][v]=true; if(!vis[v]) {vis[v]=true;q.push(v);} } } } int e[Maxe][2]; void reserveEdge() { int tm=0; For(i,n) { ForEdge(j,i) { int v=edge[j].to; e[tm][0]=v; e[tm++][1]=i; } } init_edge(); For(i,tm) { add_edge(e[i][0],e[i][1]); } } void solve() { init_edge(); For(i,m) { int u=E[i][0],v=E[i][1]; if(match[v]==u) { Res[i]=true; add_edge(v,u); //cout<<v<<" "<<u<<endl; } else { Res[i]=false; add_edge(u,v); // cout<<u<<" "<<v<<endl; } } n=X+Y; Tarjan(); Visit(0); reserveEdge(); Visit(1); top=0; For(i,m) { if(!Res[i]) { int u=E[i][0],v=E[i][1]; if(match[u]==-1 || match[v]==-1 || bleg[v]==bleg[match[u]] || canReach[0][match[u]] || canReach[1][v] ) continue; else stk[top++]=i; } } pf("%d ",top); For(i,top) { if(i) printf(" "); printf("%d",stk[i]); } puts(""); } int CTN(char c) { if(c>='0' && c<='9') return c-'0'; return (int)(c-'A')+10; } int getNum(char *str) { int u=0; For(i,3) u=u*32+CTN(str[i]); return u; } int main() { char str[20]; while(~sf("%d%d%d",&X,&Y,&m)) { n=X; init_edge(); For(i,m) { sf("%s",str); int u=getNum(str),v=getNum(str+3)+X; add_edge(u,v); //cout<<u<<" "<<v<<endl; E[i][0]=u,E[i][1]=v; } HK(); solve(); } return 0; }