poj 2135 mcmf 최소 비용 최대 흐름 (모드 테스트 문제)

그냥 자기 모판 연습 하 는 거 어때요?

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<queue>
const int inf=0x3f3f3f3f;
const int maxn=1005;
const int maxm=maxn*40;
int head[maxn];
struct notes{
    int v,c,f,next;
}a[maxm];
int coun;
bool used[maxn];
int path[maxn];
int dis[maxn];
int q[maxn];
int n,m;
int ans;

void add(int u,int v,int f,int c){
    a[coun].v=v;
    a[coun].c=c;
    a[coun].f=f;
    a[coun].next=head[u];
    head[u]=coun;
    coun++;
    a[coun].v=u;
    a[coun].c=-c;
    a[coun].f=0;
    a[coun].next=head[v];
    head[v]=coun;
    coun++;
}

bool spfa(){
    memset(path,-1,sizeof(path));
    queue<int>que;
    while(!que.empty()){
        que.pop();
    }
    memset(dis,inf,sizeof(dis));//        
    memset(used,false,sizeof(used));
    que.push(0);
    path[0]=0;
    dis[0]=0;//       0 
    used[0]=true;
    while(!que.empty()){
        int t=que.front();
        que.pop();
        used[t]=false;
        for(int i=head[t];i!=-1;i=a[i].next){//   
            int v=a[i].v,c=a[i].c;
            if(a[i].f>0&&(dis[v]>c+dis[t])){//        ，         
                dis[v]=c+dis[t];
                path[v]=t;///i
                q[v]=i;//            
                if(!used[v]){
                    used[v]=true;//         
                    que.push(v);
                }
            }
        }
    }
    if(path[n]==-1)return false;
    return true;
} 

void mcmf(){
    while(spfa()){
        int min_=inf+1;
        for(int i=n;i!=0;i=path[i]){//   n 1   ，0-1，n-n+1    
            min_=min(min_,a[q[i]].f);//        
        }
        for(int i=n;i!=0;i=path[i]){//   n 1   ，0-1，n-n+1    
            a[q[i]].f-=min_;///        q[i]       i   ，  i       ，      ，        
            a[q[i]^1].f+=min_;//        
        }
        ans+=dis[n]*min_;
    }
}

int main(){
    //freopen("2135.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=-1){
        coun=0;
        memset(head,-1,sizeof(head));
        while(m--){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            add(u,v,1,c);
            add(v,u,1,c);
        }
        add(0,1,2,0);
        add(n,n+1,2,0);
        ans=0;
        mcmf();
        printf("%d
",ans);
    }
    return 0;
}