题意：
n行， a房间的气球，b房间的气球
i行需要的气球，与a房的距离，b房的距离
求最小距离
#include#include #include #include #include #include #include #include #define N 2000#define M 10100#define inf 107374182#define ll intusing namespace std;inline ll Min(ll a,ll b){return a>b?b:a;}inline ll Max(ll a,ll b){return a>b?a:b;}int n;//双向边，注意RE 注意这个模版是 相同起末点的边 合并而不是去重struct Edge{ int from, to, flow, cap, nex, cost;}edge[M*2];int head[N], edgenum;//2个要初始化-1和0void addedge(int u,int v,int cap,int cost){//网络流要加反向弧 Edge E={u, v, 0, cap, head[u], cost}; edge[edgenum]=E; head[u]=edgenum++; Edge E2={v, u, 0, 0, head[v], -cost}; //这里的cap若是单向边要为0 edge[edgenum]=E2; head[v]=edgenum++;}int D[N], P[N], A[N];bool inq[N];bool BellmanFord(int s, int t, int &flow, int &cost){ for(int i=0;i<=n+4;i++) D[i]= inf; memset(inq, 0, sizeof(inq)); D[s]=0; inq[s]=1; P[s]=0; A[s]=inf; queue Q; Q.push( s ); while( !Q.empty()){ int u = Q.front(); Q.pop(); inq[u]=0; for(int i=head[u]; i!=-1; i=edge[i].nex){ Edge &E = edge[i]; if(E.cap > E.flow && D[E.to] > D[u] +E.cost){ D[E.to] = D[u] + E.cost ; P[E.to] = i; A[E.to] = Min(A[u], E.cap - E.flow); if(!inq[E.to]) Q.push(E.to) , inq[E.to] = 1; } } } if(D[t] == inf) return false; flow += A[t]; cost += D[t] * A[t]; int u = t; while(u != s){ edge[P[u]].flow += A[t]; edge[P[u]^1].flow -= A[t]; u = edge[P[u]].from; } return true;}int Mincost(int s,int t){ int flow = 0, cost = 0; while(BellmanFord(0, n+3, flow, cost)); return cost;}int main(){ int i,disa,disb,flow,maxa,maxb; while( scanf("%d %d %d",&n, &maxa, &maxb), n+maxb+maxa){ memset(head,-1,sizeof(head)); edgenum=0; addedge(n+1, n+3, maxa, 0); addedge(n+2, n+3, maxb, 0); for(i=1;i<=n;i++){ scanf("%d %d %d",&flow,&disa,&disb); addedge(0, i, flow, 0); addedge(i, n+1, flow, disa); addedge(i, n+2, flow, disb); } printf("%d\n",Mincost(0,n+3) ); } return 0;}/*3 15 3510 20 1010 10 3010 40 105 5 01 10 10001 10 10001 10 10000 10 10001 10 10000 0 0ans:30040*/