不得不说感觉SDOI的题都好值得回味啊
思路题:
我们应该如何规避掉重复路线
我们可以将一个点拆成两个点,一个入一个出,这样的话在十字路口就可以防止重复了
容量为一,权值为零,然后变为最小费用最大流
之后就比较裸的code了
#include<bits/stdc++.h> using namespace std; const int N=4e2+7; const int M=1e5+7; int n,m; int head[M>>1],nxt[M],to[M],cost[M],cap[M]; int _=1; void add(int x,int y,int c,int z) { _++; to[_]=y; cap[_]=c; cost[_]=z; nxt[_]=head[x]; head[x]=_; return ; } int flow[N],pre[N],xb[N],dis[N],f[N]; int mflow,mcost; void build(int fa,int ds,int co) { if(fa==1) { add(1,ds,1,co); add(ds,1,0,-co); return ; } if(ds==n) { add(fa+n,n,1,co); add(n,fa+n,0,-co); return ; } add(fa+n,ds,1,co); add(ds,fa+n,0,-co); return ; } queue<int >q; bool bfs(int s,int t) { memset(dis,127,sizeof(dis)); memset(f,0,sizeof(f)); int maxx=dis[0]; while(!q.empty()) q.pop(); fill(pre+1,pre+1+n,-1); f[s]=1; dis[s]=0; pre[s]=0; flow[s]=0x7fffffff; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); f[x]=0; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(cap[i]>0&&dis[y]>dis[x]+cost[i]) { dis[y]=dis[x]+cost[i]; pre[y]=x; xb[y]=i; flow[y]=min(flow[x],cap[i]); if(!f[y]) { f[y]=1; q.push(y); } } } } if(dis[t]>=maxx) return 0; else return 1; } void makeflow(int x,int y) { while(bfs(x,y)) { int e=y; while(e!=x) { cap[xb[e]]-=flow[y]; cap[xb[e]^1]+=flow[y]; e=pre[e]; } mflow+=flow[y]; mcost+=flow[y]*dis[y]; } return ; } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=2;i<n;i++) { add(i,i+n,1,0); add(i+n,i,0,0); } for(int i=1;i<=m;i++) { int p,w,e; cin>>p>>w>>e; build(p,w,e); } makeflow(1,n); cout<<mflow<<" "<<mcost; return 0; }