题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=569&problem=4277&mosmsg=Submission+received+with+ID+2182664

题目大意:给定一个带权有向图(v,e)，求两条互不相交的从1到v的路径(不经过同一个点)，使两条路径的权和最小.

分析:即求从1到v的最小费用流,到v的流量为2,且每个点只能经过一次.加一个从v出发的点v',费用为0,容量为2,求1到v'的最小费用流即满足前一条件;将2到v-1每个点拆分成两个点,费用为0,容量为1,再求从1到v'的最小费用流即可.

　　一定要注意求mcmf时设置的INF要恰当!!!不然就溢出然后疯狂WA了!!!

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int maxn=2005,maxm=20005,INF=1000000; 8 struct Edge{ 9     int from,to,cap,flow,cost;10     Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}11 };12 13 struct MCMF{14     int n,m;15     vector
          
            edges;16 vector
           
             G[maxn];17 int inq[maxn],d[maxn],p[maxn],a[maxn];18 19 void init(int n){20 this->n=n;21 this->m=0;22 for(int i=0;i
            
             m++);30 G[to].push_back(this->m++);31 }32 33 bool BellmanFord(int s,int t,int &flow,long long &cost){34 for(int i=0;i
             

Q;38 Q.push(s);39 while(!Q.empty()){40 int u=Q.front();Q.pop();41 inq[u]=0;42 43 for(int i=0;i

e.flow&&d[e.to]>d[u]+e.cost){46 d[e.to]=d[u]+e.cost;47 p[e.to]=G[u][i];48 a[e.to]=min(a[u],e.cap-e.flow);49 if(!inq[e.to]){Q.push(e.to);inq[e.to]=1;}50 }51 }52 }53 if(d[t]==INF)return false;54 flow+=a[t];55 cost+=(long long)d[t]*(long long)a[t];56 for(int u=t;u!=s;u=edges[p[u]].from){57 edges[p[u]].flow+=a[t];58 edges[p[u]^1].flow-=a[t];59 }60 return true;61 }62 63 int Mincost(int s,int t,long long &cost){64 int flow=0;cost=0;65 while(BellmanFord(s,t,flow,cost));66 return flow;67 }68 };69 70 int main(){71 //freopen("e:\\in.txt","r",stdin);72 int n,m,a,b,c;73 MCMF mcmf;74 mcmf.init(2*n);75 for(int i=1;i

>a>>b>>c;80 a--;b--;81 if(a==0||a==n-1){82 mcmf.AddEdge(a,b,1,c);83 }84 else{85 mcmf.AddEdge(a+n,b,1,c);86 }87 }88 mcmf.AddEdge(n-1,2*n-1,2,0);89 long long cost=0;90 mcmf.Mincost(0,2*n-1,cost);91 cout<

<