裸的費用流 源點向家引容量為2的邊 谷倉向匯點引容量為2的邊 其余的按照原圖建圖，容量為1，費用為長度 等于一共跑了兩次 直接跑費用流.
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<queue>using namespace std;const int N=10000,inf=0x3f3f3f3f;int d[N],p[N],a[N],head[N],inq[N];int te,s,t,n,m;queue<int>q;struct edge{ int u,v,cap,cost,flow,next;}e[100010];void add(int u,int v,int cap,int cost){ e[++te].u=u; e[te].v=v; e[te].cap=cap; e[te].cost=cost; e[te].next=head[u]; head[u]=te;}void insert(int u,int v,int cap,int cost){ add(u,v,cap,cost),add(v,u,0,-cost);}int spfa(int &flow,int &cost){ memset(a,0,sizeof(a)); memset(d,0x3f,sizeof(d)); memset(inq,0,sizeof(inq)); while(!q.empty())q.pop(); q.push(s);d[s]=0;inq[s]=1,a[s]=inf; while(!q.empty()) { int u=q.front(); for (int i=head[u];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow&&d[v]>d[u]+e[i].cost) { d[v]=d[u]+e[i].cost; a[v]=min(e[i].cap-e[i].flow,a[u]); p[v]=i; if (!inq[v]) { inq[v]=1; q.push(v); } } } inq[u]=0; q.pop(); } if (d[t]==inf)return false; cost+=d[t]*a[t]; flow+=a[t]; for (int u=t;u!=s;u=e[p[u]].u) { e[p[u]].flow+=a[t]; e[p[u]^1].flow-=a[t]; } return true;}int mcmf(int &cost){ int flow=0; cost=0; while(spfa(flow,cost)); return flow;}int main(){ cin>>n>>m; int u,v,cost; te=1;s=(n<<1)+1,t=(n<<1)+2; insert(s,1,2,0);insert(n,t,2,0); for (int i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&cost); insert(u,v,1,cost); insert(v,u,1,cost); } mcmf(cost); cout<<cost;}新聞熱點
疑難解答
