[AHOI2014/JSOI2014]支线剧情有上下界费用流

～～～题面～～～

题解：

第一眼费用流，，然后想了好久怎么建图，，，最后发现是最小费用可行流的板子题。。。。

其实还没有很懂这个算法，所以这里只是摆一下步骤，以后再补理解吧。

首先一个思路就是转换图，将有上下限的图变为普通的网络流图，然后再跑费用流。

所以建图其实和有上下界的网络流一样的。。。

1，首先建立超级源点汇点ss和tt

2，对于原图中每一条边x ---> y,设其上下界为(l, r),费用为cost,那么连边的时候将流量变为r - l即可

3，对于任意点i，记d[i]为它的富余流量，即入度的下界和 - 出度的下界和。

　　若d[i] > 0,则连边ss ----> i, 流量为d[i] , 费用0

　　若d[i] < 0,则连边i ----> tt,流量为-d[i],费用0

4，连边t ---> s,流量inf，费用0

答案即为ans + 所有边下界 * 边的费用

其实可以感性的理解为先有了一个不一定合法的解（下界*费用），然后再利用费用流使用最小的代价使得答案合法。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 400

 #define ac 100000

 #define inf 2139062143

 #define getchar() *o++

 char READ[], *o = READ;

 int n, ans, s, t1, t;

 int last[AC], dis[AC], disflow[AC], d[AC];

 int date[ac], Next[ac], haveflow[ac], cost[ac], Head[AC], tot = ;

 bool z[AC];

 deque<int> q;

 inline int read()

 {

     int x=;char c=getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void add(int f,int w,int S,int C)

 {

     date[++tot] = w, Next[tot] = Head[f], haveflow[tot] = S, cost[tot] = C, Head[f] = tot;

     date[++tot] = f, Next[tot] = Head[w], cost[tot] = -C, Head[w] = tot;

     //printf("%d %d %d %d\n",f,w,S,C);

 }

 void pre()

 {

     int a,b,c;

     n=read();

     t1 = n + , s = n + , t = n + ;

     for(R i=;i<=n;i++)

     {

         a=read();

         for(R j=;j<=a;j++)

         {

             b=read(),c=read();

             --d[i], ++d[b];

             ans += c;

             add(i, b, inf, c);

         }

     }

     for(R i=;i<=n;i++)

         add(i, t1, inf, );

     for(R i=;i<=n;i++)

     {

         if(d[i] > ) add(s, i, d[i], );

         if(d[i] < ) add(i, t, -d[i], );

     }

     add(t1, , inf, );//是费用为0！

 }

 inline void aru()

 {

     int x = t;

     while(x != s)

     {

         haveflow[last[x]] -= disflow[t];

         haveflow[last[x] ^ ] += disflow[t];

         x = date[last[x] ^ ];

     }

     ans += disflow[t] * dis[t];

 }

 bool spfa()

 {

     int x, now;

     dis[s] = , disflow[s] = inf, z[s] = true;

     q.push_front(s);

     while(!q.empty())

     {

         x = q.front();

         q.pop_front();

         z[x] = false;//标记出列

         for(R i=Head[x]; i ;i=Next[i])

         {

             now = date[i];

             if(haveflow[i] && dis[now] > dis[x] + cost[i])

             {//要有流量啊

                 dis[now] = dis[x] + cost[i];

                 last[now] = i;

                 disflow[now] = min(disflow[x], haveflow[i]);

                 if(!z[now])

                 {

                     z[now] = true;

                     if(!q.empty() && dis[now] < q.front()) q.push_front(now);

                     else q.push_back(now);

                 }

             }

         }

     }

     if(dis[t] != inf) aru();

     return dis[t] != inf;

 }

 bool spfa1()

 {

     int x,now;

     z[s]=true,dis[s]=,disflow[s]=inf;

     q.push_front(s);

     while(!q.empty())

     {

         x=q.front();

         q.pop_front();

         z[x]=false;

         for(int i=Head[x]; i ;i=Next[i])

         {

             now=date[i];

             if(haveflow[i] && dis[now]>dis[x]+cost[i])

             {

                 dis[now]=dis[x]+cost[i];

                 last[now]=i;

                 disflow[now]=min(disflow[x],haveflow[i]);//以点为单位记录到这个点时的流量

                 if(!z[now])

                 {

                     z[now] = true;

                     q.push_front(now);

                 }

                 /*if(!z[now] && now!=t)

                 {

                     if(!q.empty() && dis[now]<dis[q.front()])    q.push_front(now);

                     else q.push_back(now);

                     z[now]=true;

                 }*/

             }

         }

     }

     //更新路径

     if(dis[t] != inf) aru();

     return dis[t] != inf;

 }

 void work()

 {

     //printf("%d\n",ans);

     memset(dis, , sizeof(dis));

     while(spfa())

         memset(dis, , sizeof(dis));

     printf("%d\n",ans);

 }

 int main()

 {

 //    freopen("in.in","r",stdin);

     fread(READ, , , stdin);

     pre();

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

[AHOI2014/JSOI2014]支线剧情有上下界费用流

最新文章

热门文章

巴特西

[AHOI2014/JSOI2014]支线剧情 有上下界费用流

最新文章

热门文章

[AHOI2014/JSOI2014]支线剧情有上下界费用流