[Noi2008]志愿者招募网络流构图-白红宇

[Noi2008]志愿者招募网络流构图

阅读量：5322 次

发布时间：2019-06-14

本文共 1808 字，大约阅读时间需要 6 分钟。

这题简直太神了，我才知道网络流还可以这样做！

这题想了近一个小时构图，没搞出来。。

最后看了BYvoid大神的题解搞得。。

无限仰慕！

View Code

1 #include 
      
        2 #include 
       
          3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define N 2000 8 #define M 200000 9 #define INF 1e910 11 using namespace std;12 13 int head[N],next[M],to[M],len[M],pr[M];14 int dis[N],pre[N],q[M];15 bool vis[N];16 int n,m,a[N],cnt,S,T,mlen;17 18 inline void add(int u,int v,int r,int w)19 {20     to[cnt]=v; len[cnt]=r; pr[cnt]=w; next[cnt]=head[u]; head[u]=cnt++;21     to[cnt]=u; len[cnt]=0; pr[cnt]=-w; next[cnt]=head[v]; head[v]=cnt++;22 }23 24 inline void read()25 {26     memset(head,-1,sizeof head); cnt=0;27     scanf("%d%d",&n,&m);28     S=0; T=n+2;29     for(int i=1;i<=n;i++) scanf("%d",&a[i]);30     for(int i=1;i<=n;i++)31     {32         add(S,i,a[i],0);33         add(i+1,T,a[i],0);34         add(i+1,i,INF,0);35     }36     for(int i=1,b,c,d;i<=m;i++)37     {38         scanf("%d%d%d",&b,&c,&d);39         add(b,c+1,INF,d);40     }41 }42 43 inline bool spfa()44 {45     memset(pre,-1,sizeof pre);46     memset(dis,0x3f,sizeof dis);47     int h=1,t=2,sta;48     q[1]=S; dis[S]=0; vis[S]=true;49     while(h
           
            dis[sta]+pr[i])54 {55 dis[to[i]]=dis[sta]+pr[i];56 pre[to[i]]=i;57 if(!vis[to[i]]) q[t++]=to[i],vis[to[i]]=true;58 }59 }60 return pre[T]!=-1;61 }62 63 inline void updata()64 {65 mlen=INF;66 for(int i=pre[T];~i;i=pre[to[i^1]])67 mlen=min(mlen,len[i]);68 for(int i=pre[T];~i;i=pre[to[i^1]])69 len[i]-=mlen,len[i^1]+=mlen;70 }71 72 inline void go()73 {74 int ans=0;75 while(spfa()) updata(),ans+=mlen*dis[T];76 printf("%d\n",ans);77 }78 79 int main()80 {81 read();82 go();83 return 0;84 }