C.rar_C语言经典程_算法图论c语言

#include <stdio.h> //用bellman_ford找增广路，改变时增加回边，费用为负 #include <math.h> //这个算法我同陈诗毅师兄个代码对过，相同输入答案相同，不过系pku过唔到～～，希望有人指正一下 #include <string.h> #include <algorithm> #include <queue> #define N 1005 #define M 999999 using namespace std; struct points { int flow[N]; int road[N]; int turn[N]; int cost[N]; int num; }point[N]={0}; struct sea { int num,pla,pre; }; int s,t; int cost=0,flow=0; sea m[N]={0}; bool findpath() { int i,j,use,check; int d,e; int dist[N]={0}; sea mid; queue<int> que; que.push(s); check=s; memset(m,0,sizeof(m)); for(i=s;i<=t;i++) dist[i]=M; dist[s]=0; while(1) { for(i=1;i<point[check].num;i++) { d=dist[check]+point[check].cost[i]; e=abs(point[check].flow[i]); if(d<dist[(point[check].road[i])]&&e) { mid.num=check; //标号 mid.pla=i; dist[point[check].road[i]]=d; m[point[check].road[i]]=mid; que.push(point[check].road[i]); } } if(que.empty()) return false; check=que.front(); que.pop(); if(check==t) break; } return true; } int addpath() { int road[N]={0}; int i,mid,check,Min; int a,b,c; mid=0;check=t;Min=1<<30; while(1) { road[mid++]=check; check=m[check].num; if(check==s) break; } road[mid++]=s; for(i=0;i<mid-1;i++) { a=road[i]; c=point[m[a].num].flow[m[a].pla]; if(c<Min) Min=c; } for(i=0;i<mid-1;i++) { a=road[i];b=m[a].num; point[m[a].num].flow[m[a].pla]-=Min; cost+=point[m[a].num].cost[m[a].pla]*Min; if(!point[a].turn[b]) { point[a].flow[point[a].num]+=Min; point[a].cost[point[a].num]=-point[b].cost[m[a].pla]; point[a].road[point[a].num]=b; point[a].num++; point[a].turn[b]=point[a].num-1; } else {point[a].flow[point[a].turn[b]]+=Min;} } return Min; } void maxflow() { while(findpath()) { flow+=addpath(); } printf("flow=%d cost=%d\n",flow,cost); } int main() { int n,k,a,b,c,d,i; scanf("%d %d",&n,&k); for(i=1;i<=n;i++) point[i].num++; while(k--) { scanf("%d %d %d %d",&a,&b,&c,&d); point[a].flow[point[a].num]=c; point[a].road[point[a].num]=b; point[a].cost[point[a].num]=d; point[a].num++; } scanf("%d %d",&s,&t); maxflow(); scanf("%d",&a); }