对于30%的数据,N ≤ 20,M ≤ 120。
对于100%的数据,N ≤ 200,M ≤ 20000。
【思路】
拆点。我们可以将每个路口拆成两个点(i)和(i+N)。由于Ai与Bi之间有长度为C的街道,则在(Ai+N)和(Bi)之间添加一条容量为1,费用为c的边。然后对于每个Ai,添加一条(Ai,Ai+n)的边,容量为1(保证每个路口仅仅经过一次),费用为0的边。最大流即可。
要注意的是1和N不算是路口,所以(1与n+1)(n与2n)之间的边容量为INF。
#include<cstdio> #include<iostream> #define R register #define inf 0x3f3f3f3f using namespace std; int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return f?x:-x; } const int N=510,M=1e5+10; struct node{ int u,v,next,cap,cost; }e[M];int tot=1; int n,m,S,T,ans1,ans2,head[N],pree[N],prev[N],flow[N],dis[N],q[M*10]; bool vis[N]; void add(int x,int y,int cap,int cost){ e[++tot].u=x;e[tot].v=y;e[tot].cap=cap;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot; e[++tot].u=y;e[tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot; } bool spfa(){ for(int i=S;i<=T;i++) vis[i]=0,dis[i]=inf; int h=0,t=1; q[t]=S;dis[S]=0;vis[S]=1; while(h!=t){ int x=q[++h];vis[x]=0; for(int i=head[x];i;i=e[i].next){ int v=e[i].v; if(e[i].cap>0&&dis[v]>dis[x]+e[i].cost){ dis[v]=dis[x]+e[i].cost; pree[v]=i; if(!vis[v]){ vis[v]=1; q[++t]=e[i].v; } } } } return dis[T]<inf; } void augment(){ int x=inf; for(int i=pree[T];i;i=pree[e[i].u]) x=min(x,e[i].cap); ans1++; for(int i=pree[T];i;i=pree[e[i].u]){ ans2+=x*e[i].cost; e[i].cap-=x; e[i^1].cap+=x; } } int main(){ n=read();m=read();S=1;T=n<<1; for(int i=1,x,y,z;i<=m;i++){ x=read();y=read();z=read(); add(x+n,y,1,z); } for(int i=2;i<n;i++) add(i,i+n,1,0); add(1,S+n,inf,0); add(n,T,inf,0); while(spfa()) augment(); printf("%d %d",ans1,ans2); return 0; } /*zjk‘code 跑的比我快,存一下 #include<cstdio> #include<iostream> #define N 410 #define M 41000 #define inf 1000000000 using namespace std; int head[N],dis[N],q[N*10],vis[N],fa[N],n,m,S,T,cnt=1,timer,ans; struct node{ int v,pre,f,w; };node e[M]; void add(int u,int v,int f,int w){ e[++cnt].v=v;e[cnt].f=f;e[cnt].w=w;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].w=-w;e[cnt].pre=head[v];head[v]=cnt; } bool spfa(){ for(int i=1;i<=T;i++)dis[i]=inf; int h=0,t=1; q[1]=S;dis[S]=0;vis[S]=1; while(h<t){ int x=q[++h];vis[x]=0; for(int i=head[x];i;i=e[i].pre){ int v=e[i].v; if(dis[v]>dis[x]+e[i].w&&e[i].f){ dis[v]=dis[x]+e[i].w; fa[v]=i; if(!vis[v]){ q[++t]=v; vis[v]=1; } } } } return dis[T]!=inf; } void updata(){ int tmp=T; while(tmp!=S){ int l=fa[tmp],v=e[l].v; e[l].f--;e[l^1].f++; tmp=e[l^1].v; } ans+=dis[T]; } int main(){ scanf("%d%d",&n,&m); S=0,T=n*2+1; add(S,1,inf,0);add(n*2,T,inf,0); for(int i=2;i<n;i++)add(i,i+n,1,0); add(1,1+n,inf,0);add(n,n+n,inf,0); for(int i=1;i<=m;i++){ int x,y,z;scanf("%d%d%d",&x,&y,&z); add(x+n,y,1,z); } while(spfa()){ timer++;updata(); } printf("%d %d",timer,ans); return 0; }*/
原文:http://www.cnblogs.com/shenben/p/6258717.html