标签存档：图论

题意：

就是稳定婚姻系统的模板题。

对于求出来的每一组配对(a,b)，不能找到(b,c)满足b更喜欢c且c更喜欢b，对于a同样。

分析：

就使一种延迟方法，就使先让他们拍拖然后遇到更好的，就飞掉之前的伴侣。。。

有点邪恶。。。

更详细的讲解请参照：http://hi.baidu.com/leokan/blog/item/4f9b04f719993025730eecef.html

HINT:

1A。

code：

#include #include using namespace std;
int n,ml[27][27],fl[27][27],st[27],bf[27],gf[27],rank[27][27];
char mn[27],fn[27];

int pos(char ch){
    if (ch>=’a’ && ch<='z'){
      for (int i=1;i<=n;i++)
        if (mn[i]==ch) return i;
    }else   
      for (int i=1;i<=n;i++)
        if (fn[i]==ch) return i;
}

void init(){
    cin >> n;
    for (int i=1;i<=n;i++) cin >> mn[i];
    for (int i=1;i<=n;i++) cin >> fn[i];
    for (int t=1;t<=n;t++){
        char ch;
        cin >> ch;
        int i=pos(ch);
        cin >> ch;
        for (int j=1;j<=n;j++){
            cin >> ch;
            ml[i][j]=pos(ch);
        }   
    }   
    for (int t=1;t<=n;t++){
        char ch;
        cin >> ch;
        int i=pos(ch);
        cin >> ch;
        for (int j=1;j<=n;j++){
            cin >> ch;
            fl[i][j]=pos(ch);
        }   
    }   
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        rank[i][fl[i][j]]=j;
}   

void dfs(int p){
    int i;
    for (i=st[p]+1;i<=n;i++){
        if (bf[ml[p][i]]==0){
            bf[ml[p][i]]=p;
            gf[p]=ml[p][i];
            break;
        }   
        if (rank[ml[p][i]][p]            int tmp=bf[ml[p][i]];
            bf[ml[p][i]]=p;
            gf[p]=ml[p][i];
            dfs(tmp);
            break;
        }   
    }  
    st[p]=i;
}   

void work(){
    memset(st,0,sizeof(st));
    memset(bf,0,sizeof(bf));
    memset(gf,0,sizeof(gf));
    for (int i=1;i<=n;i++)
      if (gf[i]==0) dfs(i);
}   

void print(){
    for (int i=1;i<=n;i++)
      cout << mn[i] << " " << fn[gf[i]] << endl;
}   

int main(){
    int T;
    cin >> T;
    for (int i=1;i<=T;i++){
        init();
        work();
        print();
        if (i!=T) cout << endl;
    }   
}   

题意：

幼儿园里有许多房间，之间是走廊和门。一个装修计划即将执行。 这些门允许涂上明快的颜色：绿色和黄色。园长希望满足以下条件：任意一扇门的各个面必须不同颜色。每一个房间绿色门的数量，与黄色门的数量之差最多为1。给定园长的计划，请提出你的安排。

分析：

首先，对于无向图，度为奇数的点必然有偶数个。

下面证明一下：

如果加入边(i,j)，有下面几种情况：

1、两个点原来的度一奇一偶，那么加入边以后，度为奇数的点的数量没变

2、两个点原来的度都是奇数，加入边后，度为奇数的点的数量-2

3、两个点原来的度都为偶数，加入边后，度为奇数的点的数量+2

由于只有3个种情况-2,+0,+2，所以，度为奇数的点的数量必为偶数个。

于是命题得证。

然后我们对度为奇数的同一连通分量的点连边，这样就使图不存在度为奇数的点了。

于是我们利用欧拉回路可以使颜色数量相等。

最后我们把加的边删掉。

由于每个点都只会加一条边，所以G和Y的差距不会超过1。

code：

#include #include struct gtp{int color,next;}c[100000];
int g[101][101],n,ls[101][101],ct,du[101],L[100000],Lt,a[101][101],e=0,v[101];
bool flag[101];

void init(){
    memset(g,0,sizeof(g));
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        int num,tmp;
        scanf("%d",&num);
        for (int j=1;j<=num;j++){
            scanf("%d",&tmp);
            g[i][tmp]++;
        }   
    }   
}   

void dfs(int k){
    for (int i=1;i<=n;i++)
      if (a[i][k]>0){
          a[i][k]–;
          a[k][i]–;
          dfs(i);
      }   
    L[++Lt]=k;
}   

void filldfs(int k){
    for (int i=1;i<=n;i++)
      if (g[k][i]>0 && v[i]==0){
          v[i]=v[k];
          filldfs(i);
      }           
}   

void fill_color(){
    memset(v,0,sizeof(v));
    for (int i=1;i<=n;i++)
      if (v[i]==0) {
          v[i]=++ct;
          filldfs(i);
      }   
}   

void addcolor(int x,int y){
    e++;
    c[e].color=0;
    c[e].next=ls[x][y];
    ls[x][y]=e;
    e++;
    c[e].color=1;
    c[e].next=ls[y][x];
    ls[y][x]=e;
}   

void eur(){
    memset(du,0,sizeof(du));
    memcpy(a,g,sizeof(g));
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (g[i][j]>0) du[j]+=g[i][j];
    for (int i=1;i<=n;i++)
      if (du[i]%2==1)
        for (int j=i+1;j<=n;j++)
          if (du[j]%2==1 && v[i]==v[j]){
              du[i]++;
              du[j]++;
              a[i][j]++;
              a[j][i]++;
              break;
          }
    memset(flag,false,sizeof(flag));
    for (int i=1;i<=n;i++)
      if (!flag[v[i]]){
        flag[v[i]]=true;
        Lt=0;
        dfs(i);
        for (int j=1;j          addcolor(L[j],L[j+1]);
    }   
}   

void print(){
    for (int i=1;i<=n;i++){
      for (int j=1;j<=n;j++){
          int t=ls[i][j];
          for (int num=g[i][j];num>=1;num–){
              if (c[t].color==0) printf("G ");
                            else printf("Y ");
              t=c[t].next;
          }   
      }       
      printf("n");
}   
}   

int main(){
    init();
    fill_color();
    eur();
    print();
}   

题意：

给定N个点,E条边的有向图，问图中是否任意两个点u，v都有

（u能到达v）or（v能到达u）

分析：

首先环内的肯定是满足的，所以先缩点。

然后剩下一棵树。

那么从根节点（即缩点后没有入度的点）出发，假设一路走下去是一条链的话（即树没有分叉），而且所有的点都能走到，那么就满足性质。

证明：

1、如果有分叉的话，分叉两边的点不能到达对方。

2、入度为0的点不可能没有，因为已经缩点，不存在环了。

3、入度为0的如果>1，那么两个入度为0的点不能到达对方。

所以，结论就是，只有所有收缩后的点成一长链，才能满足性质。

插曲：

Tarjan居然写错了= =，真想抽自己一下

code：

#include

题意：

有N个学生，可以被分配去M个学校，给出哪些学生能去哪些学校，

求一个解：每间学校都分到>=2个学生的方案。

分析：

cai0715用上下界做。。。其实不用这么麻烦= =

连边(s,i,1) i为学生

连边(i,j,1) j为学校

连边(j,T,2)

然后最大流即可。

插曲：

PE到2B，原来SGU的PE有可能是Runtime ERROR。原来我数组没开够

code：

#include #include #define N 100000
struct gtp{int x,y,c,next,op;}g[N];
int e,n,m,ls[N],flow,cur[N],fa[N],d[N],num[N],list[N][3];

void add(int x,int y,int c){
    e++;
    g[e].x=x;
    g[e].y=y;
    g[e].c=c;
    g[e].next=ls[x];
    ls[x]=e;
    g[e].op=e+1;
   
    e++;
    g[e].x=y;
    g[e].y=x;
    g[e].c=0;
    g[e].next=ls[y];
    ls[y]=e;
    g[e].op=e-1;
}   

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        add(0,i,1);
        int num,x;
        scanf("%d",&num);
        for (int j=1;j<=num;j++){
            scanf("%d",&x);
            add(i,n+x,1);
        }
    }
    for (int i=1;i<=m;i++) add(i+n,n+m+1,2);
}   

void relabel(int k){
    int min=n+m+1;
    cur[k]=ls[k];
    for (int t=ls[k];t!=0;t=g[t].next)
        if (g[t].c>0 && d[g[t].y]    d[k]=min+1;
}   

void change(){
    int nf=2;
    for (int i=n+m+1;i!=0;i=g[fa[i]].x)
      if (g[fa[i]].c    flow+=nf;
    for (int i=n+m+1;i!=0;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }   
}   

void sap(){
    num[0]=n+m+2;
    for (int i=0;i<=n+m+1;i++) cur[i]=ls[i];
    int i=0;
    while (d[0]        while (cur[i]!=0){
            if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
            cur[i]=g[cur[i]].next;
        }
        if (cur[i]==0){
            num[d[i]]–;
            if (num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=0) i=g[fa[i]].x;
        }   
        else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==n+m+1){
                change();
                i=0;
            }   
        }   
    }
}   

void addlist(int key,int pos){
    list[pos][++list[pos][0]]=key;
}   

void print(){
    if (flow        printf("NOn");
        return;
    }   
    printf("YESn");
    for (int i=1;i      if (g[i].x==0 && g[i].c==0){
          int t=ls[g[i].y];
          while (t!=0){
              if (g[t].y>=n+1 && g[t].y<=n+m && g[t].c==0){
                  addlist(g[i].y,g[t].y-n);
                  break;
              }   
              t=g[t].next;
          }   
      }   
    for (int i=1;i<=m;i++)
        printf("2 %d %dn",list[i][1],list[i][2]);
}   

int main(){
    init();
    sap();
    print();
    return 0;
}   

题意：

给出N个点和M条边

再给出ai和bi。

ai表示删除i的所有入边的权值

bi表示删除i的所有出边的权值

然后给出那些边。

求怎样用最小的代价，删除所有的边。

分析：

详细的可以看amber的最小割论文

http://u.115.com/file/f7142414ae

过期的话就百度一下吧。。。

具体名字是《最小割模型在信息学竞赛中的应用》

就是最小点权覆盖（用最少的点权覆盖所有的边）

我们把每个点拆成两个点。

对于每个bi，建边(S,i,bi)

对于每个ai，建边(i+n,T,ai)

然后每条图中的边，建边(i,j+n,INF)

然后求最大流，最后求最小割即可。

插曲：

一开始ai和bi弄反了。WA到SB了

code：

#include #include #define N 100000
#define E 2000000
#define INF 0x7FFFFFFF
using namespace std;
struct edge{int x,y,c,op,next;}g[E];
int n,e=0,ls[N],fa[N],cur[N],d[N],num[N],v[N],ans[N];

void add(int x,int y,int c){
       e++;
       g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
       e++;
       g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

void init(){
     memset(ls,0,sizeof(ls));
     memset(fa,0,sizeof(fa));
     memset(cur,0,sizeof(cur));
     memset(d,0,sizeof(d));
     memset(num,0,sizeof(num));
     memset(v,0,sizeof(v));
     int m,x,y;
     cin >> n >> m;
     for (int i=1;i<=n;i++){
         cin >> x;
         add(i+n,n+n+1,x);
     }
     for (int i=1;i<=n;i++){
         cin >> x;
         add(0,i,x);
     }
     for (int i=1;i<=m;i++){
         cin >> x >> y;
         add(x,y+n,INF);
     }
}

void relabel(int k){
     cur[k]=ls[k];
     int min=n+n+1;
     for (int i=ls[k];i!=0;i=g[i].next)
       if (g[i].c>0 && d[g[i].y]     d[k]=min+1;
}

int change(){
    int nf=INF;
    for (int i=n+n+1;i!=0;i=g[fa[i]].x)
      nf=min(nf,g[fa[i]].c);
    for (int i=n+n+1;i!=0;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }
    return nf;
}

int sap(){
    int flow=0;
    for (int i=0;i<=n+n+1;i++) cur[i]=ls[i];
    num[0]=n+n+2;
    int i=0;
    while (d[0]          for (;cur[i]!=0;cur[i]=g[cur[i]].next)
              if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
          if (cur[i]==0){
            if (–num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=0) i=g[fa[i]].x;
          }
          else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==n+n+1){
              flow+=change();
              i=0;
            }
          }
    }
    return flow;
}

void dfs(int k){
     d[k]=1;
     v[k]=0;
     for (int i=ls[k];i!=0;i=g[i].next)
       if (d[g[i].y]==0 && g[i].c>0) dfs(g[i].y);
}

void print(){
     int t=0;
     for (int i=0;i<=N;i++) v[i]=1;
     memset(d,0,sizeof(d));
     dfs(0);
     for (int i=1;i<=e;i=i+2)
       if (v[g[i].x]==0 && v[g[i].y]==1 && g[i].c==0)
         ans[t++]=i;
     cout << t << endl;
     for (int i=0;i       if (g[ans[i]].x==0) cout << g[ans[i]].y << " -" << endl;
                      else cout << g[ans[i]].x-n<<" +" << endl;
}

int main(){
    init();
    int flow=sap();
    cout << flow << endl;
    print();
}