CF-717G-Underfail（费用流）

题意：http://codeforces.com/problemset/problem/717/G

给出一个母串，m个子串，同一个子串在母串的同一个位置只能匹配一次，成功匹配可以获得vi的值，母串的每个位置也有最多使用次数k。
问你最大值。
思路：

见FileRecv春**解.docx
  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\Input.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr strcat
 13 #include <string>
 14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 #include <cassert>
 21 #include <iomanip>
 22 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 23 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 24 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 25 //******************
 26 clock_t __START,__END;
 27 double __TOTALTIME;
 28 void _MS(){__START=clock();}
 29 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 30 //***********************
 31 #define rint register int
 32 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 33 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 34 #define mem(a,b) memset(a,b,sizeof(a))
 35 #define pr printf
 36 #define sc scanf
 37 #define ls rt<<1
 38 #define rs rt<<1|1
 39 typedef pair<int,int> PII;
 40 typedef vector<int> VI;
 41 typedef unsigned long long ull;
 42 typedef long long ll;
 43 typedef double db;
 44 const db E=2.718281828;
 45 const db PI=acos(-1.0);
 46 const ll INF=(1LL<<60);
 47 const int inf=(1<<30);
 48 const db ESP=1e-9;
 49 const int mod=(int)1e9+7;
 50 const int N=(int)1e6+10;
 51 
 52 struct node{
 53     int to;//这条边的终点
 54     int cap;//这条边的流量（是指当前还能流的最大流量，而不是不变量）
 55     int coc;//coc存反向边。由于我使用了vector，所以coc记录的是data[x][i]中的i。具体怎么计算反向边下面说。
 56     int cost;//cost存一条边的费用
 57 };//使用一个结构体存储所有的边以及反向边，所有边都是无向边。
 58 vector<node>data[N];//data用来存图
 59 int dx[N],pre1[N],pre2[N],incf[N],n,m,S,T,m_cost,maxf;
 60 bool inq[N];
 61 // dx，inq的意义和spfa中的dist，inq（或vis）相同，pre1，pre2，incf的用处下面会说。
 62 // n,m,S,t如题目所示，ans是最小费用，maxf是最大流。
 63 void add(int u,int v,int w,int f){//加一条边的函数，由u到v连一条流为w，花费为f的边
 64     data[u].push_back((node){v,w,data[v].size(),f});
 65     data[v].push_back((node){u,0,data[u].size()-1,-f});//反向边的流要置为0。因为如果你设成正的，这条路就有可能由终点向起点流，在另一条路上达到最大流，更小费用。这显然不合法。
 66     //反向边的实现，是考虑到这两条互为反向边的边是同时加入的，直接调用当时data[v].size()就是反向边的编号。
 67     //按说用size()计算编号是应该-1的（因为编号由0开始，而size()由1开始），但是第一个计算不用，原因是
 68     //当时v还没有插入这个边，天然有一个被减一的size()
 69 }
 70 bool spfa(){
 71     fill(dx+1,dx+n+1,N);//初始化，一定别忘了。
 72     queue<int>q;
 73     memset(inq,0,sizeof(inq));
 74     q.push(S);
 75     dx[S]=0;
 76     inq[S]=1;//以上这些变量，玩转spfa的你一定看起来很熟悉QAQ
 77     incf[S]=N;//那么incf呢？他记录的是一条增广路的最小流量。incf[i]代表当前增广路到i为止的最小流量，incf[T]为整条路最小流量。
 78     //如何理解呢，我们考虑短板效应，最大容量取决于最短木板。增广路亦然，它的最大流量取决于增广路上流量最小的边。
 79     while(!q.empty()){
 80         int now=q.front();
 81         inq[now]=0;
 82         q.pop();//是不是超熟悉的感觉QAQ (只说一下和spfa不一样的代码的意思)
 83         for(int i=0;i<data[now].size();i++){
 84             node &tmp=data[now][i];
 85             if(tmp.cap>0&&tmp.cost+dx[now]<dx[tmp.to]){//有流量才能松弛~
 86                 dx[tmp.to]=dx[now]+tmp.cost;//和spfa一样
 87                 incf[tmp.to]=min(incf[now],tmp.cap);//更新增广路的“短板”。
 88                 pre1[tmp.to]=now;//pre1[i]是这次增广路的i点是由哪个点流过来的。
 89                 pre2[tmp.to]=i;//pre2[i]是这次增广路的i点是由pre1[i]的编号为多少的边流过来的。
 90                 if(!inq[tmp.to]){//QAQ spfa，spfa你还活着！
 91                     inq[tmp.to]=1;
 92                     q.push(tmp.to);
 93                 }
 94             }
 95         }
 96     }
 97     return dx[T]!=N;//如果dx[T]被更过了，意味着一定不是最大流！返回1，找增广路去！
 98 }
 99 void update(){//更新答案和图程度的能力。
100     int x=T;//首先把当前点置为终点，我们沿着终点由增广路反向走到起点~
101     while(x!=S){//x到s的时候停止~
102         int y=pre1[x];//使用我们先前维护的数组来反向走增广路。
103         int i=pre2[x];
104         data[y][i].cap-=incf[T];//所有增广路上的边一律减去可扩最大容量！
105         data[x][data[y][i].coc].cap+=incf[T];//反向边，一律增加这个容量。
106         //如果说为什么要弄反向边，我个人的理解是：增广一条增广路费用最优，然而最大流量未必。
107         //如果我们反向建边，可以由终点流向起点，这样其实意味着，当年这条边选择的流减少一点。
108         //不过我们未必要理性理解这个事，既然都建了反向边了，那就和正向边反着来呗~
109         x=y;//迭代一下
110     }
111     maxf+=incf[T];//更新最大流
112     m_cost+=dx[T]*incf[T];//更新费用
113 }
114 void FT(){
115     while(spfa()){//当spfa发现有增广路的时候，就更新一下图，最小费用和最大流。如果没有增广路，答案最优。
116         update();
117     }
118 }
119 /*
120     最小费用流其实并不难，而且非常好用/w可以解决很多乱七八糟的问题。
121     代码难度较低，建图难度较高。如SDOI2017新生舞会。
122     个人认为，用这样鬼畜的建模方式，恐怕难以卡掉spfa。
123     为什么找增广路用spfa就可以做到最小费用呢？考虑我们每一次的松弛都是以一条路径的方式松弛过来的，尽管
124     会发散出去，但松弛到一个指定的终点一定有且只有一条路。如果已经不可松弛，这条路一定是当前单位流量价格
125     最小的增广路。我们贪心：反正都是增广路，先扩便宜的肯定好啊QAQ
126 */
127 
128 char s[N],ts[N];
129 
130 int main(){
131     sc("%d",&n);
132     n++;
133     S=0,T=n;
134     sc("%s",s+1);
135     sc("%d",&m);
136     for(int i=1;i<=m;i++)
137     {
138         int p;
139         sc("%s%d",ts+1,&p);
140         int l=strlen(ts+1);
141         for(int j=1;j+l-1<=n-1;++j)
142         {
143             bool ok=1;
144             for(int k=1;k<=l;++k)
145             {
146                 if(s[j+k-1]!=ts[k])break;
147                 if(k==l)
148                     add(j,j+l,1,-p);
149             }
150         }
151     }
152     int x;
153     sc("%d",&x);
154     for(int i=1;i<=n-1;++i)add(i,i+1,x,0);
155     add(0,1,x,0);
156     FT();//最小费用流主体
157 //    cout<<maxf<<" "<<m_cost<<endl;
158     pr("%d
",-m_cost);
159 }