NC51280. 舞动的夜晚
描述
L公司和H公司举办了一次联谊晚会。
晚会上，L公司的N位员工和H公司的M位员工打算进行一场交际舞。
在这些领导中，一些L公司的员工和H公司的员工之间是互相认识的，这样的认识关系一共有T对。
舞会上，每位员工会尝试选择一名Ta认识的对方公司的员工作为舞伴，并且每位员工至多跳一支舞。
完成的交际舞的数量越多，晚会的气氛就越热烈。
顾及到晚会的气氛，员工们希望知道，哪些员工之间如果进行了交际舞，就会使整场晚会能够完成的交际舞的最大数量减小。
输入描述
第一行三个整数N、M、T。
接下来T行每行两个整数x、y，表示L公司的员工x和H公司的员工y互相认识
输出描述
第一行一个整数cnt，表示进行了交际舞后会使整场晚会能够完成的交际舞的最大数量减小的员工有多少对。
第二行cnt个整数，升序输出这样的一对员工的认识关系的编号（他们的认识关系是在输入数据中读入的第几条认识关系）。
如果cnt=0，输出一个空行。
示例1
输入:
3 3 6 1 1 2 1 2 2 3 1 3 2 3 3
输出:
3 2 4 5
C++14(g++5.4) 解法, 执行用时: 110ms, 内存消耗: 6008K, 提交时间: 2019-09-24 17:02:03
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e4+10;
const int M=1e5+10+N;
int head[N],ver[2*M],edge[2*M],nex[2*M],tot=1;
inline void add(int x,int y,int z) {
ver[++tot]=y;
edge[tot]=z;
nex[tot]=head[x];
head[x]=tot;
}
//int n,m;
int s,t,d[N];
bool bfs() {
memset(d,0,sizeof(d));
d[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()) {
int x=q.front();
q.pop();
for(int i=head[x]; i; i=nex[i])
if(edge[i]&&!d[ver[i]]) {
d[ver[i]]=d[x]+1;
q.push(ver[i]);
if(ver[i]==t)
return true;
}
}
return false;
}
int dinic(int x,int flow) {
if(x==t)
return flow;
int rest=flow,k;
for(int i=head[x]; i&&rest; i=nex[i])
if(edge[i]&&d[ver[i]]==d[x]+1) {
k=dinic(ver[i],min(rest,edge[i]));
if(!k)
d[ver[i]]=0;
edge[i]-=k;
edge[i^1]+=k;
rest-=k;
}
return flow-rest;
}
int dfn[N],low[N],num,stk[N],top,ins[N],c[N],cnt;
void tarjan(int x) {
dfn[x]=low[x]=++num;
stk[++top]=x;
ins[x]=1;
for(int i=head[x]; i; i=nex[i]) {
if(!edge[i])continue;
int y=ver[i];
if(!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]) {
++cnt;
do {
ins[stk[top]]=0;
c[stk[top]]=cnt;
} while(stk[top--]!=x);
}
}
int a[M],b[M],edge_id[M],v[M];
int main() {
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
for(int i=1; i<=p; ++i) {
int x,y;
scanf("%d%d",&x,&y);
y+=n;
add(x,y,1);
edge_id[i]=tot;
add(y,x,0);
a[i]=x;
b[i]=y;
}
s=0;
t=n+m+1;
for(int i=1;i<=n;++i)
add(s,i,1),add(i,s,0);
for(int i=1+n;i<=m+n;++i)
add(i,t,1),add(t,i,0);
int maxflow=0,flow;
while(bfs())
while(flow=dinic(s,INF))
maxflow+=flow;
for(int i=0;i<=n+m+1;++i)
if(!dfn[i])
tarjan(i);
int ans=0;
for(int i=1;i<=p;++i)
if(edge[edge_id[i]]&&c[a[i]]!=c[b[i]])
v[i]=++ans;
printf("%d\n",ans);
for(int i=1;i<=p;++i)
if(v[i])printf("%d ",i);
return 0;
}
C++ 解法, 执行用时: 125ms, 内存消耗: 6008K, 提交时间: 2022-04-21 12:53:30
#include<bits/stdc++.h>
#define Opt(x) printf("%d\n",x)
#define speread() freopen("data.in","r",stdin)
using namespace std;
typedef long long ll;
const int M=2e5+10,N=2e4+10;
const double eps=1e-5;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
int n,m,p,s,t;
int head[N],ver[M*2],nxt[M*2],edge[M*2],edgeid[M],tot=1;
int a[M],b[M],col[N],v[M];
int d[N],dfn[N],low[N],st[N],ins[N],top,num,cnt,ans,maxflow,flow;
void add(int x,int y,int z){ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;}
bool bfs(){
memset(d,0,sizeof(d));d[s]=1;
queue<int>que;
que.push(s);
while(que.size()){
int x=que.front();que.pop();
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(z&&!d[y]){
d[y]=d[x]+1;
que.push(y);
if(y==t)return true;
}
}
}
return false;
}
int dinic(int x,int flow){
if(x==t)return flow;
int rest=flow,k;
for(int i=head[x];i&&rest;i=nxt[i]){
int y=ver[i],z=edge[i];
if(z&&d[y]==d[x]+1){
k=dinic(y,min(rest,z));
if(!k)d[y]=0;
edge[i]-=k;
edge[i^1]+=k;
rest-=k;
}
}
return flow-rest;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x;
ins[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(!z)continue;
if(!dfn[y])tarjan(y),low[x]=min(low[y],low[x]);
else if(ins[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
++cnt;
int y;
do{y=st[top--];ins[y]=0;col[y]=cnt;}while(x-y);
}
}
int main(){
cin>>n>>m>>p;
for(int i=1,x,y;i<=p;i++)cin>>x>>y,y+=n,add(x,y,1),edgeid[i]=tot,add(y,x,0),a[i]=x,b[i]=y;
s=0,t=n+m+1;
for(int i=1;i<=n;i++)add(s,i,1),add(i,s,0);
for(int i=n+1;i<=n+m;i++)add(i,t,1),add(t,i,0);
while(bfs())while(flow=dinic(s,INF))maxflow+=flow;
for(int i=s;i<=t;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=p;i++)if(edge[edgeid[i]]&&col[a[i]]!=col[b[i]])v[i]=++ans;
printf("%d\n",ans);
for(int i=1;i<=p;i++)if(v[i])printf("%d ",i);
}