试题库问题(最大流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[N];
void init();
void add_edge(int u,int v,int c);
void add(int u,int v,int c);
void set_h(int t,int n);
int Isap(int s,int t,int n);
void print(int m,int n);

int main(int argc,char**argv){
    int n,m,sum=0,total;
    int cost,num;//sum 需要的总题目数量
    cout<<"输入题型数m和试题总数n:n";
    cin>>m>>n;
    init();
    total=m+n;
    cout<<"请依次输入每种题型选择的数量n";
    for(int i=1;i<=m;i++){
        cin>>cost;
        sum+=cost;
        add(0,i,cost);
    }
    cout<<"输入每个试题所属的题型(0结束)n";
    for(int j=m+1;j<=total;j++){
        while(cin>>num,num){//num为题目j的题型号码
            add(num,j,1);
        }
        add(j,total+1,1);//试题j到汇点的边的容量为1，因为每个题目只能选一次
    }
    if(sum==Isap(0,total+1,total+2)){
        //输出方案
        print(m,n);
    }else{
        cout<<"无法实现分配n";
    }
    return 0;
}


void init(){
    memset(V,-1,sizeof(V));//初始化V[all].first=-1
    top=0;//记录E[]使用到了那里了
}
//-->
void add_edge(int u,int v,int c){//添加单条边
    //参数 u v及u-->v边的容量c
    E[top].v=v;
    E[top].cap=c;
    E[top].flow=0;
    //头插法
    E[top].next=V[u].first;
    V[u].first=top;
    top++;
}
void add(int u,int v,int c){//添加正负两边
    add_edge(u,v,c);
    add_edge(v,u,0);
}
//-->
void set_h(int t,int n){//标高函数,t源点 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<<"Init hight Valuen";
    cout<<"h[ ]=";
    for(int i=1;i<=n;i++){
        cout<<" "<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]){
                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;
            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 print(int m,int n){
    //遍历中间层的边,边流量为1的则是选择中的题目
    for(int i=1;i<=m;i++){//遍历每个题型
        cout<<"第"< 
测试样例 
4 15
2 0 3 2
1 2 0
2 3 0
1 4 0
2 3 0
2 4 0
1 2 3 0
3 0
4 0
4 0
2 3 4 0
3 0
2 0
1 0
1 4 0
4 0
 
样例结果 
输入题型数m和试题总数n:
4 15
请依次输入每种题型选择的数量
2 0 3 2
输入每个试题所属的题型(0结束)
1 2 0
2 3 0
1 4 0
2 3 0
2 4 0
1 2 3 0
3 0
4 0
4 0
2 3 4 0
3 0
2 0
1 0
1 4 0
4 0
Init hight Value
h[ ]= 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 -1
增广路径:20---19---4---0增流: 1
增广路径:20---18---4---0增流: 1
增广路径:20---15---3---0增流: 1
增广路径:20---14---3---0增流: 1
增广路径:20---11---3---0增流: 1
重贴标签后的高度
h[ ]= 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 0 -1
增广路径:20---17---1---0增流: 1
增广路径:20---10---1---0增流: 1
重贴标签后的高度
h[ ]= 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 0 -1
第1个题型选中的题目:13 6
第2个题型选中的题目:
第3个题型选中的题目:11 10 7
第4个题型选中的题目:15 14

--------------------------------
Process exited after 2.153 seconds with return value 0
请按任意键继续. . .