关于网络流算法

  1 #include<iostream>
  2 #include<string.h>
  3 #include<vector>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int maxm=10000+100;    //最大点数
  9 const int INF=0x3f3f3f3f;
 10 
 11 struct edge{        //边：起点、终点、容量、流量、单位费用
 12     int from,to,c,f,cost;
 13     edge(int a,int b,int m,int n,int p):from(a),to(b),c(m),f(n),cost(p){}
 14 };
 15 
 16 int aabs(int a){
 17     return a>=0?a:-a;
 18 }
 19 
 20 struct MCMF{
 21     int m,s,t;
 22     vector<edge> e;
 23     vector<int> g[maxm];
 24     int dis[maxm],a[maxm],p[maxm];
 25     bool vis[maxm];
 26 
 27     void init(int n){        //初始化函数
 28         for(int i=0;i<=n;i++)g[i].clear();
 29         e.clear();
 30     }
 31 
 32     void add(int a,int b,int c,int v){    //加边函数
 33         e.push_back(edge(a,b,c,0,v));
 34         e.push_back(edge(b,a,0,0,-v));
 35         m=e.size();
 36         g[a].push_back(m-2);
 37         g[b].push_back(m-1);
 38     }
 39 
 40     bool spfa(int& flow,int& cost){
 41         memset(dis,0x3f,sizeof(dis));
 42         memset(vis,0,sizeof(vis));
 43         queue<int>q;
 44         q.push(s);
 45         vis[s]=1;
 46         dis[s]=0;
 47         p[s]=0;
 48         a[s]=INF;
 49         while(!q.empty()){
 50             int u=q.front();q.pop();
 51             vis[u]=0;
 52             for(int i=0;i<g[u].size();i++){
 53                 edge tmp=e[g[u][i]];
 54                 if(dis[tmp.to]>dis[u]+tmp.cost &&tmp.c>tmp.f){
 55                     dis[tmp.to]=dis[u]+tmp.cost;
 56                     p[tmp.to]=g[u][i];
 57                     a[tmp.to]=min(a[u],tmp.c-tmp.f);
 58                     if(!vis[tmp.to]){
 59                         q.push(tmp.to);
 60                         vis[tmp.to]=1;
 61                     }
 62                 }
 63             }
 64         }
 65         if(dis[t]==INF)return 0;
 66         flow+=a[t];
 67         cost+=dis[t]*a[t];
 68         int u=t;
 69         while(u!=s){
 70             e[p[u]].f+=a[t];
 71             e[p[u]^1].f-=a[t];
 72             u=e[p[u]].from;
 73         }
 74         return 1;
 75     }
 76 
 77     void MF(int s,int t,int &flow,int &cost){    //调用的计算最小费用函数
 78         this->s=s;
 79         this->t=t;
 80         //int flow=0,cost=0;
 81         while(spfa(flow,cost));
 82         //return cost;
 83     }
 84 
 85 };
 86 
 87 int main()
 88 {
 89     freopen("C:\\Users\\lenovo\\Desktop\\工作\\华为挑战赛\\testCase0\\testCase4.txt", "r", stdin);
 90     
 91     //数据准备 
 92     int n, m, s, t, h;
 93     int from, to, cap, value;
 94     int flow, cost, need;
 95     int loc[maxm], k;
 96     MCMF mcmf;
 97     
 98     //输入第一行 
 99     cin>>n>>m>>h;
100     //初始化 
101     mcmf.init(n+h+2);
102     //输入网络节点并且add 
103     for( int i=1; i<=m; i++ )
104     {
105         cin>>from>>to>>cap>>value;
106         mcmf.add(from, to, cap, value);
107         mcmf.add(to, from, cap, value);
108     }
109     //输入消费结点、add零费用边、建立超级汇点 
110     for( int i=1; i<=h; i++ )
111     {
112         cin>>to>>from>>cap;
113         mcmf.add(from, to+n, cap, 0);
114         mcmf.add(to+n, from, cap, 0); 
115         
116         mcmf.add(to+n, n+h+1, cap, 0);    //汇点编号为 n+h+1 
117         mcmf.add(n+h+1, to+n, cap, 0);
118     }
119     //建立超级源点（以0结点为服务器）
120     k=2;
121     memset(loc,-1,sizeof(loc));
122     loc[0]=0;    loc[1]=1;
123     for(int i=0;i<k;i++)
124     {
125         mcmf.add(n+h+2, loc[i], cap, 0);    //源点编号为 n+h+2
126         mcmf.add(loc[i], n+h+2, cap, 0);
127     }
128     
129     mcmf.MF(n+h+1,n+h+2,flow,cost);
130     cout<<"flow= "<<flow<<endl<<"cost= "<<cost<<endl;
131     
132     fclose(stdin);
133 }
134 //多（固定）服务器单消费节点，含有超级结点 

10 14 2

0 1 1 2
0 9 2 3
1 2 3 1
1 4 4 2
4 9 5 3
9 8 6 1
4 2 7 2
2 6 8 3
4 5 9 1
5 6 10 3
8 6 11 1
6 7 12 2
6 3 13 3
7 3 14 2

0 2 100
1 9 100