以前太naive了，对着蓝书写vector存边，常数惊人。

今天拿链表重写了一遍。

话说把结果输出写到析构函数里好好玩，可以调戏同学：

“喂，你看啊，我的程序没输出喔~”

（掩面）

 

Dinic:

 

1 #include
     
        2 #include
      
         3   4 #define INF 0x3f3f3f3f  5 #define MAXN 10005  6 #define MAXM 100005  7   8 #define minn(a,b) ((a)<(b)?(a):(b))  9  10 int n,m; 11  12 struct Dinic{ 13     int s,t; 14      15     int flow,cost; 16     int cnt,head[MAXN],next[MAXM<<1|1]; 17     int dis[MAXN],cur[MAXN]; 18      19     std::queue
       
         Q; 20      21     struct Edge{ 22         int u,v,c,f; 23          24         Edge(){} 25         Edge(int u,int v,int c,int f):u(u),v(v),c(c),f(f){} 26     }e[MAXM<<1|1]; 27      28     Dinic(){ 29         for(int i=0;i
        
         ed.f&&dis[ed.v]==0) 57                     dis[ed.v]=dis[u]+1,Q.push(ed.v); 58             } 59         } 60          61         return dis[t]; 62     } 63      64     int DFS(int u,int res){ 65         if(u==t||res==0) return res; 66          67         int fff=0; 68         for(int &i=cur[u];i!=-1;i=next[i]){ 69             Edge &ed=e[i]; 70              71             if(ed.c>ed.f&&dis[u]+1==dis[ed.v]){ 72                 int f=DFS(ed.v,minn(ed.c-ed.f,res)); 73                  74                 fff+=f,res-=f; 75                 ed.f+=f,e[i^1].f-=f; 76                  77                 if(res==0) break; 78             } 79         } 80          81         return fff; 82     } 83      84     void solve(){ 85         while(BFS()){ 86             for(int i=0;i<=n;++i) cur[i]=head[i]; 87             flow+=DFS(s,INF); 88         } 89     } 90 }; 91  92 Dinic a; 93  94 int main(){ 95     scanf("%d%d%d%d",&n,&m,&a.s,&a.t); 96      97     register int x,y,z; 98     for(register int i=0;i
        
       
      
     

 

 

MCMF:

 

1 #include
     
        2 #include
      
         3   4 #define INF 0x3f3f3f3f  5 #define MAXN 5005  6 #define MAXM 50005  7   8 #define minn(a,b) ((a)<(b)?(a):(b))  9  10 int n,m; 11  12 struct MCMF{ 13     int s,t; 14      15     int flow,cost; 16     int cnt,head[MAXN],next[MAXM<<1|1]; 17     int dis[MAXN],res[MAXN],pre[MAXN]; 18      19     bool inq[MAXN]; 20      21     std::queue
       
         Q; 22      23     struct Edge{ 24         int u,v,c,f,cost; 25          26         Edge(){} 27         Edge(int u,int v,int c,int f,int cost):u(u),v(v),c(c),f(f),cost(cost){} 28     }e[MAXM<<1|1]; 29      30     MCMF(){ 31         for(int i=0;i<=MAXN;++i) head[i]=-1; 32     } 33     ~MCMF(){ 34         printf("%d %d\n",flow,cost); 35     } 36      37     inline void addedge(int u,int v,int c,int cost){ 38         e[cnt]=Edge(u,v,c,0,cost); 39         next[cnt]=head[u]; 40         head[u]=cnt++; 41          42         e[cnt]=Edge(v,u,0,0,-cost); 43         next[cnt]=head[v]; 44         head[v]=cnt++; 45     } 46      47     inline bool SPFA(){ 48         for(int i=0;i<=n;++i) dis[i]=INF,inq[i]=false; 49         dis[s]=0,inq[s]=true,res[s]=INF,Q.push(s); 50          51         while(Q.empty()==false){ 52             int u=Q.front(); 53             Q.pop(),inq[u]=false; 54              55             for(int i=head[u];i!=-1;i=next[i]){ 56                 Edge &ed=e[i]; 57                  58                 if(ed.c>ed.f&&dis[ed.v]>dis[u]+ed.cost){ 59                     dis[ed.v]=dis[u]+ed.cost; 60                     res[ed.v]=minn(ed.c-ed.f,res[u]); 61                     pre[ed.v]=i; 62                      63                     if(!inq[ed.v]) 64                         Q.push(ed.v),inq[ed.v]=true; 65                 } 66             } 67         } 68          69         if(dis[t]==INF) return false; 70          71         flow+=res[t]; 72         cost+=res[t]*dis[t]; 73          74         for(int u=t;u!=s;u=e[pre[u]].u){ 75             e[pre[u]].f+=res[t]; 76             e[pre[u]^1].f-=res[t]; 77         } 78          79         return true; 80     } 81      82     inline void solve(){ 83         while(SPFA()); 84     } 85 }; 86  87 MCMF a; 88  89 int main(){ 90     scanf("%d%d%d%d",&n,&m,&a.s,&a.t); 91      92     register int u,v,c,cost; 93     for(int i=1;i<=m;++i){ 94         scanf("%d%d%d%d",&u,&v,&c,&cost); 95         a.addedge(u,v,c,cost); 96     } 97      98     a.solve(); 99     100     return 0;101 }