题目描述的很清楚,转化一下就是,0为源点,n+d+1为终点,1->N为牛点,N+1->N+D为食物点,从0到1->N容量为k,从N+1->N+D到n+d+1容量为Di,加上1容量,OK,直接用Dinic算法切掉。
犯了一个错,if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){,等号写成赋值了,看了半天,呵呵!以后要小心罗,这种错误不值得!
 
代码实现如下:
#include <iostream>
#include <fstream>
using namespace std;
//Problems – 2002 Winter Open, Green (Senior Division)
//Problem 2 – New years party
const int MAXN=310, MAXE=21000;
typedef struct Edge{
    int i, j, next, op, f, c;
};
Edge es[MAXE];
int eid=0, n, d, k, nt, first[MAXN], pre[MAXN], ptr[MAXN], queue[MAXN], first1[MAXN];
bool visited[MAXN];
//declaration
void addEdge(int i, int j, int c);
int Dicnic();
void bfslevel();
void dfs_maxflow();
//implemenation, eid=0, reset
void addEdge(int i, int j, int c){
    es[eid].i=i, es[eid].j=j, es[eid].f=0, es[eid].c=c;
    es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
    es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;//reverse non-sense
    es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
}
void bfslevel(){
    for(int i=0; i<=nt; i++) pre[i]=INT_MAX;
    int top=0, size=1; queue[top]=0, pre[0]=0;
    while(top<size){
        int cn=queue[top++];
        if(cn==nt) return;
        for(int e=first[cn]; e!=-1; e=es[e].next){
            if(pre[es[e].j]>pre[cn]+1){//in the residental graph
                if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){
                    queue[size++]=es[e].j, pre[es[e].j]=pre[cn]+1;
                }
            }
        }
    }
}
void dfs_maxflow(){
    memcpy((void*)first1, (void*)first, sizeof(first));
    memset((void*)visited, 0, sizeof(visited));
    int top=0; queue[0]=0;
    while(top>-1){
        if(queue[top]==nt){
            int fmin=INT_MAX, value;
            for(int i=top; i>0; i–){
                if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
                    if((value=es[ptr[queue[i]]].c-es[ptr[queue[i]]].f)<fmin) fmin=value;
                }
                if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
                    if((value=es[ptr[queue[i]]].f)<fmin) fmin=value;
                }
            }
            //update maxflow
            for(int i=top; i>0; i–){
                if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
                    es[ptr[queue[i]]].f+=fmin, es[es[ptr[queue[i]]].op].f+=fmin;
                }
                if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
                    es[ptr[queue[i]]].f-=fmin, es[es[ptr[queue[i]]].op].f-=fmin;
                }
            }
            return;//break;
        }
        else{
            int tp=queue[top], tmp=first1[tp];
            for(;tmp!=-1;tmp=es[tmp].next){
                if(!visited[es[tmp].j]){
                    if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&pre[es[tmp].j]==pre[tp]+1){
                        first1[tp]=es[tmp].next;
                        queue[++top]=es[tmp].j, ptr[es[tmp].j]=tmp;
                        break;
                    }
                }
            }//for
            if(tmp==-1){visited[tp]=true; top–;}
        }
    }
}
int Dicnic(){
    while(true){
        bfslevel();
        if(pre[nt]==INT_MAX) break;
        dfs_maxflow();
    }
    //get maxflow for source output
    int maxflow=0;
    for(int e=first[0]; e!=-1; e=es[e].next){
        maxflow+=es[e].f;
    }
    return maxflow;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int dtoT, m, ntod;
    cin>>n>>k>>d; nt=n+d+1, memset((void*)first, 0xff, sizeof(first));
    for(int i=1; i<=n; i++) addEdge(0, i, k);//, cout<<0<<" "<<i<<" "<<k<<endl;//add 0->Ni for k
    for(int i=1; i<=d; i++){
        cin>>dtoT, addEdge(i+n, nt, dtoT);//, cout<<i+n<<" "<<nt<<" "<<dtoT<<endl;
    }
    for(int i=1; i<=n; i++){
        cin>>m;
        for(int j=1; j<=m; j++){
            cin>>ntod, addEdge(i, ntod+n, 1);//, cout<<i<<" "<<ntod+n<<" "<<1<<endl;
        }
    }
    cout<<Dicnic()<<endl;
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
 
2.航天飞机实验[算法导论P427,lrjP317]
最大流最小割解题:最大流确实是很强的工具,有点喜欢最高余流的算法,几行就搞定问题,而且思路直观!
自己写了个测试数据:
10 6 [仪器数,试验数]
1 2 3 4 5 6 [每个试验的净收入]
1 2 3 4 5 6 7 8 9 2 [每个仪器的维护费用]
4 1 2 5 7 [试验1的对应仪器]
3 4 7 8
4 9 7 3 5
3 1 9 6
5 1 4 8 9 3
3 3 6 9
证明:首先要证明最大流就是其收入最大值,先建立模型,将仪器作为源点的邻接点,而将试验作为目标点的邻接点,作一个二分,其权值分别为仪器支付费用,以及
试验净收入。如图

一个基本判断是,对于一个基本割集T,若Ei在其中,那么对应的Ii也应该在T中。[无穷边不可能在最小割中]
1,最小割边不可能通过+无穷边;
2,必定有一个最小割集合的容量,sum(Ii)+sum(Ej),若Ii是在T集中的,那么Ii肯定计算在最小割的值中了;而对应的Ej则没有计算在最小割中,所以Ii为运输的仪器,而Ej为没有参加的试验;转化一下,和净收入是一致的,因此最大流就是其净收入。
因此,直接用预流推进求出最大流,然后用Df求出T集即可。[理论写在最大流最小割的扩展应用部分中]。
 
代码实现:[in和原来的文件流名一样了,只有改下了,写代码的时候,还是要注意变量命名的,太随意了]
#include <iostream>
#include <fstream>
using namespace std;
const int MAXE=150, MAXN=40;
typedef struct Edge{
    int i, j, next, f, c, op;
};
Edge es[MAXE];
int eid=0, first[MAXN], l[MAXN], hv[MAXN], ev[MAXN];
int in, en, n;
bool inS[MAXN];
//declaration
void addEdge(int i, int j, int c);
void Hpreflow();
void initailflow();
void discharge(int u);
bool push(int eid);
bool relabel(int u);
void dfsforS(int v);
//implementation
void addEdge(int i, int j, int c){
    if(!c) return;
    es[eid].i=i, es[eid].j=j, es[eid].f=0, es[eid].c=c;
    es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
    es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;
    es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
}
void Hpreflow(){
    initailflow();
    int pos=0, u=l[pos];
    while(u!=-1){
        int oldh=hv[u];
        discharge(u);
        if(oldh<hv[u]){//relabel it
            if(pos!=0) l[pos]^=l[0], l[0]^=l[pos], l[pos]^=l[0];
            pos=0;
        }
        u=l[++pos];
    }
}
//initial for preflow
void initailflow(){
    memset((void*)hv, 0, sizeof(hv)), memset((void*)ev, 0, sizeof(ev)),
    memset((void*)l, 0xff, sizeof(l));
    for(int i=0; i<n-1; i++) l[i]=i+1;//l->1…n-1
    hv[0]=n;
    for(int e=first[0]; e!=-1; e=es[e].next){
        if(es[e].c>0){//for preflow
            es[e].f+=es[e].c, es[es[e].op].f+=es[e].c;
            ev[0]-=es[e].c, ev[es[e].j]+=es[e].c;
        }
    }
}
//discharge for node u;
void discharge(int u){
    int tmp=first[u];
    while(ev[u]>0){
        if(tmp==-1) relabel(u), tmp=first[u];
        else if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&hv[u]==hv[es[tmp].j]+1)
            push(tmp);//u is higher than es[tmp].j, just one unit
        else tmp=es[tmp].next;
    }
}
bool push(int eid){
    if(ev[es[eid].i]<=0||hv[es[eid].i]!=hv[es[eid].j]+1) return false;
    int dt;
    if(es[eid].c>es[eid].f){
        dt=min(ev[es[eid].i], es[eid].c-es[eid].f);
        es[eid].f+=dt, es[es[eid].op].f+=dt;
        ev[es[eid].i]-=dt, ev[es[eid].j]+=dt;
        return true;
    }
    if(es[eid].c==-1&&es[eid].f>0){
        dt=min(ev[es[eid].i], es[eid].f);
        es[eid].f-=dt, es[es[eid].op].f-=dt;//only reverse flow here!
        ev[es[eid].i]-=dt, ev[es[eid].j]+=dt;
        return true;
    }
    return false;
}
bool relabel(int u){//relabel for node u
    int hmin=INT_MAX; bool minV=true;
    for(int e=first[u]; e!=-1; e=es[e].next){
        if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){//in the residental graph
            if(hv[es[e].j]<hv[u]) minV=false;
            if(hv[es[e].j]<hmin) hmin=hv[es[e].j];
        }
    }
    if(minV&&hmin<=n){ hv[u]=hmin+1; return true;}
    return false;
}
void dfsforS(int v){
    inS[v]=true;
    for(int e=first[v]; e!=-1; e=es[e].next){
        if(es[e].c>es[e].f){//forward-edge
            dfsforS(es[e].j);
        }
    }
}
#define fbase
int main()
{
#ifdef fbase
    ifstream inf("input.txt");
    if(!inf) return EXIT_FAILURE;
    cin.rdbuf(inf.rdbuf());
#endif
    //implementation
    int cap, t;
    cin>>in>>en, n=in+en+1;
    eid=0, memset((void*)first, 0xff, sizeof(first)),
    memset((void*)inS, 0, sizeof(inS));
    for(int i=1; i<=en; i++) cin>>cap, addEdge(in+i, n, cap);
    for(int i=1; i<=in; i++) cin>>cap, addEdge(0, i, cap);
    for(int i=1; i<=en; i++){
        cin>>cap;
        for(int j=1; j<=cap; j++) cin>>t, addEdge(t, i+in, INT_MAX);
    }
    //finish create map;
    Hpreflow();
    dfsforS(0);
    int maxflow=0;
    for(int e=first[0]; e!=-1; e=es[e].next){
        maxflow+=es[e].f;
    }
    cout<<"total profit : "<<maxflow<<endl;
    for(int i=1; i<n; i++){
        if(!inS[i]){
            if(i<=in) cout<<"I"<<i<<" ";
            else cout<<"E"<<(i-in)<<" ";
        }
    }
    cout<<endl;
#ifdef fbase
    inf.close();
#endif
    return 0;
}
#undef fbase

Advertisements