圆桌问题 网络流Isap算法

图片来源《趣学算法》 人民邮电出版社 陈小玉

图片来源《趣学算法》 人民邮电出版社 陈小玉

#include
#include
#include
#include
using namespace std;

const int INF=0x3fffffff;
const int N=100;
const int M=10000;
int top;
int h[N],pre[N],g[N];
struct Vertex{
    int first;
}V[N];
struct Edge{
    int v,next;
    int cap,flow;
}E[M];
void init();//初始化
void add(int u,int v,int c);
void add_edge(int u,int v,int c);
void printGraph(int n);//输出邻接表
int Isap(int s,int t,int n);//匹配算法
void set_h(int t,int n);
void printResult(int m,int n);//输出结果 


int main(int argc,char**argv){
    init();
    int n=0,m=0,sum=0,total=0;//sum为总人数
    int cost=0;
    cout<<"输入代表团数量m与会议桌数量n:";
    cin>>m>>n;
    total=m+n; 
    cout<<"输入每个代表团的人数n";
    for(int i=1;i<=m;i++){
        cin>>cost;
        sum+=cost;
        add(0,i,cost);//源点到代表团的边,容量为代表团人数量
    }
    cout<<"输入每个会议桌可安排的人数n";
    for(int j=m+1;j<=total;j++){
        cin>>cost;
        add(j,total+1,cost);//会议桌到汇点的边的容量为会议桌可安排的数量
    }
    //架设代表团到会议桌的边
    for(int i=1;i<=m;i++){
        for(int j=m+1;j<=total;j++){
            add(i,j,1);//容量为1，因为每个桌子上只能有一个代表团的人
        }
    }
    printGraph(total+2);
    if(sum==Isap(0,total+1,total+2)){//不能有人落单没有分配到桌子
        cout<<"会议桌安排成功n";
        printResult(m,n);
    }else{
        cout<<"无法合理分配n";
    }
    return 0;
}

//初始化
void init(){
    memset(V,-1,sizeof(V));//初始化每个结点的first为-1，初始化邻接表
    top=0;//边列表递增序号，存储边的列表使用多少了
}

//添加网络边
void add(int u,int v,int c){
    add_edge(u,v,c);//cap=c
    add_edge(v,u,0);//flow=0
}
void add_edge(int u,int v,int c){
    E[top].v=v;//邻接表插入新节点，头插法
    E[top].cap=c;
    E[top].flow=0;
    E[top].next=V[u].first;
    V[u].first=top++;
}

//匹配算法

int Isap(int s,int t,int n){
    set_h(t,n);//进行标高
    int ans=0,u=s;//ans最大流量,u当前探索到的结点
    int d;
    while(h[s]v
            //判断是否满足探索条件：有可增量 且 h[u]-1=h[v]
            if(E[i].cap>E[i].flow&&h[u]-1==h[v]){//有可增量，且层级-1
                u=v;//满足条件则当前位置移到v           E[i]
                pre[v]=i;//设置v结点的前驱为i 即记录边u------->v
                //迭代最小增量
                d=min(d,E[i].cap-E[i].flow);
                if(u==t){//探索到了汇点
                    printf("增广路径:%d",t);
                    while(u!=s){
                        int j=pre[u];//即增广路汇点的前驱边E[j]
                        E[j].flow+=d;//E[j]流量增d
                        E[j^1].flow-=d;//j的反向边流量-d
                        
                        u=E[j^1].v;
                        cout<<"---"<E[j].flow){//有可增量
                    hmin=min(hmin,h[E[j].v]);
                }
            }
            h[u]=hmin+1;//可行邻接边的中的最小高度+1，否则将走不通的点的高度为节点个数 
            printf("重贴标签后的高度n");
            printf("h[ ]=");
            for(int i=1;i<=n;i++){
                printf(" %d",h[i]);
            }
            printf("n");
            ++g[h[u]];//重新贴标签后该高度的结点数+1
            if(u!=s){//当前结点不是源点
                u=E[pre[u]^1].v;//退回一步
            }
        }
    }
    return ans;
}


//广度优先标高函数 
void set_h(int t,int n){
    queueQ;//广度优先搜索
    memset(h,-1,sizeof(h));//初始化各结点的高为-1
    memset(g,0,sizeof(g));//全部高度的结点数量为0
    h[t]=0;//汇点高度为0
    Q.push(t);//汇点入队列
    while(!Q.empty()){
        int v=Q.front();Q.pop();//对头出队列
        ++g[h[v]];//高度为h[v]的数量+1
        for(int i=V[v].first;i!=-1;i=E[i].next){//遍历结点v的临界点及v-->some
            int u=E[i].v;
            if(h[u]==-1){//还没有标记过
                h[u]=h[v]+1;
                Q.push(u);//入队列
            }
        }
    }
    cout<<"初始化标高";
    cout<<"h={";
    for(int i=0;i