二分图最大匹配必须边

• 基本..方法？
• 两道题吧
  • • poj1486
    • 洛谷3731

基本..方法？

大概就是先求出最大匹配（网络流…匈牙利会错【捂脸】），然后在残留网络上跑tarjan。然后最后看最初匹配中每条边的是不是在一个强连通里，如果不在那它就是最大匹配必须边

emmm只能二分图中…

两道题吧

不过这两道题啊…不是一天写的【捂脸】..风格看起来有很多差别【捂脸】

poj1486

• 题意

  poj1486

  有n个正方形，n个数字在图中，数字包含在正方形中，内个正方形能匹配一个数字。问都匹配上的时候，哪些数字和正方形是必须匹配成一起的

  嗯这题…又让我pe了好久（再见）

• 代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 100
#define inf 0x7fffffff
struct node{int x,y,z,next;}mp[N*N],b[N];
struct node1{int x1,x2,y1,y2;}a[N];
int n,num,t,T=,h[N],d[N],cur[N],dfn[N],low[N],belong[N],vis[N],stack[N],scc,tot,top,ans;
bool cmp(node x,node y){return x.x<y.x;}
void insert(int x,int y){
    mp[++num].x=x;mp[num].y=y;mp[num].z=;mp[num].next=h[x];h[x]=num;
    mp[++num].x=y;mp[num].y=x;mp[num].z=;mp[num].next=h[y];h[y]=num;
}
bool bfs(){
    memset(d,,sizeof(d));d[]=;
    queue<int>q;q.push();
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=mp[i].next){
            int v=mp[i].y;
            if(mp[i].z && !d[v]){
                d[v]=d[u]+;
                q.push(v); 
            }
        }
    }return d[t];
}
int dfs(int x,int s1){
    if(x==t || !s1) return s1;
    int s2=s1;
    for(int &i=cur[x];i;i=mp[i].next){
        int y=mp[i].y;
        if(d[y]==d[x]+ && mp[i].z){
            int s=dfs(y,min(mp[i].z,s1));
            mp[i].z-=s;mp[i^].z+=s;s1-=s;
            if(!s) d[y]=;
            if(!s1) return s2;
        }
    }return s2-s1;
}
void tarjan(int x){
    dfn[x]=++tot;low[x]=tot;vis[x]=;stack[++top]=x;
    for(int i=h[x];i;i=mp[i].next){
        int y=mp[i].y;if(!mp[i].z) continue;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }if(low[x]==dfn[x]){
        belong[x]=++scc;vis[x]=;
        while(stack[top]!=x){
            belong[stack[top]]=scc;
            vis[stack[top--]]=;
        }top--;
    }
}
int main(){
    while(scanf("%d",&n) && n>){
        T++;printf("Heap %d\n",T);
        memset(h,,sizeof(h));num=;t=*n+;
        for(int i=;i<=n;i++) scanf("%d%d%d%d",&a[i].x1,&a[i].x2,&a[i].y1,&a[i].y2);
        for(int i=;i<=n;i++){
            int x,y;scanf("%d%d",&x,&y);
            for(int j=;j<=n;j++) if(a[j].x1<=x && x<=a[j].x2 && a[j].y1<=y && y<=a[j].y2) insert(j,i+n);
        }
        for(int i=;i<=n;i++) insert(,i),insert(i+n,*n+);
        ans=;while(bfs()){memcpy(cur,h,sizeof(h));ans+=dfs(,inf);}
        if(ans!=n){printf("none\n\n");break;}
        memset(dfn,,sizeof(dfn));scc=top=tot=ans=;
        for(int i=;i<=t;i++) if(!dfn[i]) tarjan(i);
        memset(b,,sizeof(b));
        for(int i=;i<=num;i+=){
            int x=mp[i].x,y=mp[i].y;if(mp[i].z || x== || y==t)continue;
            if(belong[x]!=belong[y]) b[++ans].x=x,b[ans].y=y-n;
        }sort(b+,b+ans+,cmp);
        if(ans==) printf("none\n");
        else{
            for(int i=;i<=ans;i++) printf("(%c,%d) ",b[i].x+'A'-,b[i].y);printf("\n");
        }printf("\n");
    }
    return ;
}
           

洛谷3731

• 题意

  lg3731

  这题说的特别复杂，简单来说，就是有n个城市，他们之间有m条边是未连通的。求连通这m条边中的哪一条能使得图中的最大团变大（这些城市最多能被分成2个团）

• 题解

  最大团=（补图）最大独立子集

  而二分图中 最大独立子集=结点数-最大匹配数

  所以想要最大团变大，也就需要补图中最大匹配数变小

  所以..也就是求最大匹配的必须边…

  不过这题..要先dfs求出点属于哪边的…

  en这题的数据范围..我又写错了（再见）改了好久（再见） en好几天（再见）

• 代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 11000 
#define M 200000
#define inf 0x7fffffff
struct node{int x,y,next;}edge[*M];
struct node1{int x,y,z,next;}mp[*M];
struct node2{int x,y;}ans[M];
int n,m,num=,cnt=,nn=,tot=,top=,scc=,h1[N],h[N],d[N],b[N],cur[N],dfn[N],low[N],belong[N],vis[N],stack[N];
bool cmp(node2 x,node2 y){return x.x<y.x || (x.x==y.x && x.y<y.y);}
void insert(int x,int y){
    edge[++num].x=x;edge[num].y=y;edge[num].next=h1[x];h1[x]=num;
    edge[++num].x=y;edge[num].y=x;edge[num].next=h1[y];h1[y]=num;
}
int add(int x,int y,int z){
    mp[++cnt].x=x;mp[cnt].y=y;mp[cnt].z=z;mp[cnt].next=h[x];h[x]=cnt;
    mp[++cnt].x=y;mp[cnt].y=x;mp[cnt].z=;mp[cnt].next=h[y];h[y]=cnt;
}
void dfs(int x){
    for(int i=h1[x];i;i=edge[i].next){
        int y=edge[i].y;
        if(b[y]==-){b[y]=b[x]^;dfs(y);}
    }
}
bool bfs(){
    memset(d,,sizeof(d));d[]=;
    queue<int>q;q.push();
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=mp[i].next){
            int v=mp[i].y;
            if(!d[v] && mp[i].z){
                d[v]=d[u]+;
                q.push(v);
            }
        }
    }return d[n+];
}
int dfs(int x,int s1){
    if(x==n+ || !s1) return s1;
    int s2=s1;
    for(int &i=cur[x];i;i=mp[i].next){
        int y=mp[i].y;
        if(mp[i].z && d[y]==d[x]+){
            int s=dfs(y,min(mp[i].z,s1));
            s1-=s;mp[i].z-=s;mp[i^].z+=s;
            if(!s) d[y]=;
            if(!s1) return s2;
        }
    }return s2-s1;
}
void tarjan(int x){
    dfn[x]=++tot;low[x]=tot;vis[x]=;stack[++top]=x;
    for(int i=h[x];i;i=mp[i].next){
        int y=mp[i].y;if(!mp[i].z) continue;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }if(dfn[x]==low[x]){
        vis[x]=;belong[x]=++scc;
        while(stack[top]!=x){
            vis[stack[top]]=;
            belong[stack[top--]]=scc;
        }top--;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        insert(x,y);
    }
    memset(b,-,sizeof(b));
    for(int i=;i<=n;i++) 
        if(b[i]==-){
            b[i]=;
            dfs(i);
        }
    for(int i=;i<=*m-;i+=){
        int x=edge[i].x,y=edge[i].y; 
        if(!b[x]) add(x,y,);
        else add(y,x,);
    }
    for(int i=;i<=n;i++) if(b[i]) add(i,n+,);else add(,i,);
    while(bfs()){memcpy(cur,h,sizeof(cur));dfs(,inf);}
    for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=;i<=*m+;i+=)
        if(mp[i].z && belong[mp[i].x]!=belong[mp[i].y]){
            if(mp[i].x<mp[i].y) ans[++nn].x=mp[i].x,ans[nn].y=mp[i].y;
            else ans[++nn].x=mp[i].y,ans[nn].y=mp[i].x;
        }sort(ans+,ans+nn+,cmp);  
    printf("%d\n",nn);
    for(int i=;i<=nn;i++) printf("%d %d\n",ans[i].x,ans[i].y); 
    return ;
}