说在前面

网络流学的真的是很爽啊，每次一道题都要敲上百行，各种模板套上去就好，费用流虽然还不是太熟练，但是也写了几道题练手。

费用流：

费用流和最大流相比，就是多了费用这一点，而这种求法主要是利用SPFA进行求最短路和增广路，如果求出出来增广路，那么这不但是一个最大流，还是费用最小（最大）的费用流。

  • 最大流问题要求从源点S流出尽可能多的流量，流过一条或多条边，到达汇点T，且每条边上流过的流量不大于该边的流量限制，一个单位的流在某条边上产生的费用等于边的费用。而最小费用最大流问题就是要求在流量达到最大的情况下，总费用最小。

  • 由最大流的相关知识可知，当且仅当不存在S到T的增广路时，图中的流达到最大。那么我们可以每次从S流出一个单位的流量到达T，使得这个单位流量所产生的费用最小。

  • 从“形”的角度观察这个问题，每个单位的流在当前网络中产生的最小费用，等价于当前网络中S到T的最小权值路径的权值，即S到T最短路的长度。因此，可以用SPFA求最短路，每次选择残留网络中最短的增广路进行增广，直到不存在增广路为止，可以证明找到的最大流的费用一定最小。分析这个算法的时间复杂度，如果增广次数是w，每次SPFA算法在残留网络G上的运行时间是 SPFA(G), 那么总的复杂度就是 O(w*SPFA(G));

还是怕出题老师卡SPFA啊，到时候能卡成 O(N*N) 就不好玩了。

P1670传纸条

题目描述：

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

  • 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

  • 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

输入：

  1. 输入第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。
  2. 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

输出：

输出共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

题解：

  • 这道题其实就是费用流的一个模板题，我们将这道题想成网络流的题目，在源点处将其流量限制成2，那么就确定了只有两条路可以走，这也就符合了题意，那么我们在求一遍最大流的所有路径就是可以走的路径，但是要输出两路上传递纸条学生的好心程度和最大值，那么我们在用增广路径增广的时候，优先选择路径上权值和最大的路径进行增广，但是增广的前提条件就是这里是有流的QAQ，虽然这个算法和Dinic的复杂度看起来差不多，但是我感觉没有Dinic快的说。

  • 这个最短路的算法是基于SPFA的用三角形关系式来更新路径的最小/最大值，然后记录下来这两个点之间的更新的最后路径值，分别由两个值，LastPoint和LastEdge两个数组存储下来更新出来的最短路径（权值最大），具体方法就是每次在满足三角形关系式之后，记录下来当前点和自己链接的上一个点，然后记录下来链接的边的len的值。

  • 记录下来路径之后，我们再进行增广路径，沿着存下来的最短路径（权值最大）更改相对应的边的流量值，然后用总的答案值 ans 加上这个最短路的（权值最大）长度，也就是从这条更新出来的的路两点之间的Value值乘上相对应的流量（可能有些题目权值不是用流量计算的，而是固定的，那么就直接在最后加上dis[T]就好了。），最后直到没有办法求出来权值最大的路径（没有增广路），就是最终要求的值了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
using namespace std;
struct Edge
{
    int Point;
    int Value;
    int Flow;
    int Next;
    int Back;
}a[200000];
int Link[20000],Queue[200000],dis[20000];
int len,That,ans=0,n,m,S,T;
int LastPoint[20000],LastEdge[20000];
bool vis[20000];
inline int In()
{
    int This=0,F=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=This*10+ch-'0';
        ch=getchar();
    }
    return This*F;
}
void AddEdge(int x,int y,int flow,int value)
{
    a[++len].Point=y;
    a[len].Next=Link[x];
    a[len].Value=-value;
    a[len].Flow=flow;
    a[len].Back=len+1;
    Link[x]=len;
    a[++len].Point=x;
    a[len].Next=Link[y];
    a[len].Value=value;
    a[len].Flow=0;
    a[len].Back=len-1;
    Link[y]=len;
}
bool SPFA()
{
    memset(vis,false,sizeof(vis));
    memset(dis,12,sizeof(dis));
    dis[1]=0; vis[1]=true;
    Queue[1]=1;
    int head=0,tail=1;
    while(++head<=tail)
    {
        int Top=Queue[head];
        for(int i=Link[Top];i;i=a[i].Next)
        if(a[i].Flow&&(dis[Top]+a[i].Value<dis[a[i].Point]))
        {
            if(!vis[a[i].Point])
            {
                Queue[++tail]=a[i].Point;
                vis[a[i].Point]=true;
            }
            dis[a[i].Point]=dis[Top]+a[i].Value;
            LastPoint[a[i].Point]=Top;
            LastEdge[a[i].Point]=i;
        }
        vis[Top]=false;
    }
    return dis[T]!=202116108;
}
void Change()
{
    int Find=123456789;
    for(int i=T;i!=S;i=LastPoint[i])
    if(a[LastEdge[i]].Flow<Find)
    Find=a[LastEdge[i]].Flow;
    for(int i=T;i!=S;i=LastPoint[i])
    {
        a[LastEdge[i]].Flow-=Find;
        a[a[LastEdge[i]].Back].Flow+=Find;
        ans+=Find*(-a[LastEdge[i]].Value);
    }
}
int main()
{
    n=In(); m=In();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        int xx=i*m-m+j;
        int yy=xx*2; xx=yy-1;
        That=In();
        AddEdge(xx,yy,1,That);
        if(j<m) AddEdge(yy,yy+1,1,0);
        if(i<n) AddEdge(yy,yy+2*m-1,1,0);
    }
    S=1; T=n*m*2-1;
    a[1].Flow=2;
    while(SPFA()) Change();
    cout<<ans<<endl;
    return 0;
}

P1673餐巾

题目描述：

某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。
你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

输入：

第1行为n,a,b,f,fA,fB.
第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）

输出：

最少费用

题解：

  • 这道题，完全是我自己想出来的，但是有一个小小的bug，在写AddEdge来建立邻接表的时候，因为没有将反向边的价值这位-v，而是0.所以在退流的过程中，费用并没有退掉，结果每次计算答案的时候都是比标准答案大一些。整整查了一下午（话说在传纸条那道题我也没退费用，但是直接A掉了，看来有些数据还是挺水的。）

  • 这道题我们的难点就是建图，只要建好图我们跑一遍最小费用最大流就好了。所以说在这道题目中，我们获得毛巾的途径有三条，要么自己买，要么用前面剩下的，要么用消过毒的。

  • 前面剩下的很好理解，我们只需要将i和i+1进行连接边就好。那么自己买也很简单，直接建立一条流量为正无穷，费用为f的边连接源点和每一天。那么重点就是通过消毒过来的。直接将一个点向下连接两个消毒的边显然是不可行的，那么就直接拆点，将拆的点和源点连接一条流量为当天所需的毛巾量。然后连接两条不同的消毒边，到下面的天数里面，流量为正无穷，费用为两种不同的消毒方法所需要的不同的费用。

  • 总得来说就是连接源点和每一天，然后每一天和下一天连接，然后新建一个点和源点相连，然后连接可以到达消毒过后的那一天，最后每一天和汇点连接一条流量为毛巾需求量的边。

  • 那么到现在我们就将图建立起来了，很容易就可以AC掉。一定要记得退回费用！！！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cctype>
#include<string>
#include<iomanip>
using namespace std;
struct Edge
{
    int Point;
    int Next;
    int Value;
    int Back;
    int Flow;
}a[200000];
int n,A_long,B_long,A_Price,B_Price;
int Towel_Price,Link[4000],LastPoint[4000];
int Queue[200000],Maxx,LastEdge[4000];
int len,ans,Number,dis[4000];bool vis[4000];
inline int Read()
{
    int This=false,F=true; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
int AddEdge(int x,int y,int v,int f)
{
    a[++len].Point=y;
    a[len].Value=v;
    a[len].Flow=f;
    a[len].Next=Link[x];
    a[len].Back=len+1;
    Link[x]=len;
    a[++len].Point=x;
    a[len].Value=-v;//在退流的时候，同样需要返回相对应的费用！！！
    a[len].Flow=0;
    a[len].Back=len-1;
    a[len].Next=Link[y];
    Link[y]=len;
}
bool SPFA()
{
    memset(dis,20,sizeof(dis));
    memset(vis,false,sizeof(vis));
    int head=false,tail=true;
    dis[true]=false; vis[true]=true;
    int Ford=dis[false];
    Queue[true]=true;
    while(++head<=tail)
    {
        int Top=Queue[head];
        for(int i=Link[Top];i;i=a[i].Next)
        if(a[i].Flow&&(dis[Top]+a[i].Value<dis[a[i].Point]))
        {
            if(!vis[a[i].Point])
            {
                Queue[++tail]=a[i].Point;
                vis[a[i].Point]=true;
            }
            dis[a[i].Point]=dis[Top]+a[i].Value;
            LastEdge[a[i].Point]=i;
            LastPoint[a[i].Point]=Top;
        }
        vis[Top]=false;
    }
    return dis[Maxx]!=Ford;
}
void Change()
{
    int Find=2123456789;
    for(int i=Maxx;i!=true;i=LastPoint[i])
    Find=min(Find,a[LastEdge[i]].Flow);
    for(int i=Maxx;i!=true;i=LastPoint[i])
    {
        ans+=Find*(a[LastEdge[i]].Value);
        a[LastEdge[i]].Flow-=Find;
        a[a[LastEdge[i]].Back].Flow+=Find;
    }
}
int main()
{
    freopen("a.in","r",stdin);
    n=Read(); A_long=Read();
    B_long=Read();Towel_Price=Read();
    A_Price=Read(); B_Price=Read();
    Maxx=n+n+2;
    for(int i=1;i<=n;i++)
    {
        Number=Read();
        AddEdge(1,i+1,Towel_Price,2123456789);
        AddEdge(i+1,Maxx,0,Number);
        AddEdge(1,i+n+1,0,Number);
        if(i<n) AddEdge(i+1,i+2,0,123456789);
        if(i<n-A_long) AddEdge(i+n+1,i+A_long+2,A_Price,2123456789);
        if(i<n-B_long) AddEdge(i+n+1,i+B_long+2,B_Price,2123456789);
    }
    while(SPFA()) Change();
    cout<<ans<<endl;
    return 0;
}

P1674修车

题目描述：

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入：

第一行有两个数M,N，表示技术人员数与顾客数。接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

输出：

最小平均等待时间，答案精确到小数点后2位。

题解：

  • 这道题深深的告诉了我练习好模板的重要性，一会就过去将网络流所有的模板都总结下来！！！这道题最后模板写错了，导致一直Debug不出来，我在这样子下去会GG的啊。

  • 这道题的难点还是在建图，最后看了黄学长的博客里面的题解才A掉，来总结一下。首先这道题的常规的建图方法肯定是不行的，因为每一个顾客修车的先后顺序不一样的话，他们等待的时间就是不一样的，所以我一直在想如何进行建图优化，但是想了很久都没有想到，最后看了数据范围，才开始决定大胆的进行暴力。

  • 这道题边的数量是非常多的，因为他对应的情况是非常多的，既然对应不同的修车顺序不一样，他的等待的时间都不一样，那么我们本着大胆暴力的原则，将所有可能的情况全部连接成边，也就是说，我们将m个修车工人进行分身，分身成n*m个，然后每个点表示的是我是第i个工人，我修的是倒数第j辆车。

  • 这样我们就有可能将所有的情况全部的情况列举出来了，对于每一个分过身的点，我们将其和每辆车进行连接，也就是说，如果我是第i个工人，修的是我修过全部的倒数第j辆车，然后我连接的是编号为k的车，这样的话表示的就是第i个工人以倒数第j的进度开始修编号为k的车。对于这样的每一条边，我们将他的费用设为单独修这辆车的费用乘上他是倒数第几开始修的，流量为1.然后我们将所有的车连接到汇点，边的流量为1，费用为0。然后将源点和所有的工人分身相连，边的流量为1，费用为0.

  • 这样一个完整的图就建立起来了……QAQ还有，最重要的就是一定要检查自己的模板是不是敲得是对的！！！好了我要去练习模板了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iomanip>
using namespace std;
struct Edge
{
    int Point;
    int Next;
    int Value;
    int Back;
    int Flow;
}a[4000000];
int len,Link[200000],Queue[4000000],dis[200000];
int LastEdge[200000],LastPoint[200000],ans,Maxx;
int n,m,Time[200][2000];
bool vis[200000];
inline int Read()
{
    int This=0,F=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
void AddEdge(int x,int y,int v,int f)
{
    a[++len].Point=y;
    a[len].Next=Link[x];
    a[len].Value=v;
    a[len].Back=len+1;
    a[len].Flow=f;
    Link[x]=len;
    a[++len].Point=x;
    a[len].Next=Link[y];
    a[len].Value=-v;
    a[len].Back=len-1;
    a[len].Flow=0;
    Link[y]=len;
}
bool SPFA()
{
    memset(vis,false,sizeof(vis));
    memset(dis,20,sizeof(dis));
    Queue[true]=true; int Ford=dis[true];
    int head=false,tail=true;
    vis[true]=true; dis[true]=false;
    while(++head<=tail)
    {
        int Top=Queue[head];
        for(int i=Link[Top];i;i=a[i].Next)
        if(a[i].Flow&&(dis[Top]+a[i].Value<dis[a[i].Point]))
        {
            if(!vis[a[i].Point])
            {
                Queue[++tail]=a[i].Point;
                vis[a[i].Point]=true;
            }
            dis[a[i].Point]=dis[Top]+a[i].Value;
            LastEdge[a[i].Point]=i;
            LastPoint[a[i].Point]=Top;
        }
        vis[Top]=false;
    }
    return dis[Maxx]!=Ford;
}
void Change()
{
    int Find=2123456789;
    for(int i=Maxx;i!=true;i=LastPoint[i])
    Find=min(Find,a[LastEdge[i]].Flow);
    for(int i=Maxx;i!=true;i=LastPoint[i])
    {
        a[LastEdge[i]].Flow-=Find;
        a[a[LastEdge[i]].Back].Flow+=Find;
        ans+=Find*(a[LastEdge[i]].Value);
    }
}
int main()
{
    n=Read(); m=Read();
    Maxx=n*m+m+2;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    Time[i][j]=Read();
    for(int i=1;i<=n*m;i++)
    AddEdge(1,i+1,0,1);
    for(int i=1;i<=m;i++)
    AddEdge(n*m+i+1,Maxx,0,1);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int k=1;k<=m;k++)
    AddEdge((i-1)*m+j+1,n*m+1+k,Time[k][i]*j,1);
    while(SPFA()) Change();
	cout<<setiosflags(ios::fixed)<<setprecision(2);
    cout<<(double)(ans/(1.0*m))<<endl;
    return 0;
}