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

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;

const int MAXN = 510,MAXM = 100000;

struct Edge{
  int from,to;
  int cap,flow;
  int cost,nex;
}edge[MAXM*2];
int fir[MAXN],ecnt = 2;
void addedge(int a,int b,int c,int d){
  // printf("add:%d %d %d %d\n",a,b,c,d);
  edge[ecnt] = (Edge){a,b,c,0,d,fir[a]};
  fir[a] = ecnt++;
  edge[ecnt] = (Edge){b,a,0,0,-d,fir[b]};
  fir[b] = ecnt++;
}

int dis[MAXN],vis[MAXN],minf[MAXN],pree[MAXN];
queue<int> q;

bool spfa(int s,int t){
  while(!q.empty()) q.pop();
  memset(dis,0x3f,sizeof(dis));
  memset(vis,0,sizeof(vis));
  q.push(s);dis[s] = 0,minf[s] = inf;
  while(!q.empty()){
    int nown = q.front();q.pop();
    vis[nown] = 0;
    for(int nowe = fir[nown];nowe;nowe =  edge[nowe].nex){
      Edge & e = edge[nowe];
      if(dis[e.to] > dis[nown] + e.cost && e.cap > e.flow){
        dis[e.to] = dis[nown] + e.cost;
        minf[e.to] = min(minf[nown],e.cap - e.flow);
        pree[e.to] = nowe;
        if(vis[e.to] == 0){
          q.push(e.to);
          vis[e.to] = 1;
        }
      }
    }
  }
  return dis[t] < inf;
}

int min_cost_flow(int s,int t,int k = inf){
  int ans = 0;
  while(spfa(s,t) && k > 0){
    if(dis[t] > 0) break;
    for(int nown = t,nowe = 0;nown != s;nown = edge[nowe].from){
      nowe = pree[nown];
      edge[nowe].flow += minf[t],edge[nowe^1].flow -= minf[t];
    }
    ans += dis[t] * minf[t];
  }
  return ans;
}
int n,m,k;
char s[MAXN];
char t[MAXN];

bool check(int pos,int len){
  if(pos + len - 1 > n) return 0;
  for(int i = 1;i<=len;i++) if(s[pos + i - 1] != t[i]){
    return 0;
  }
  return 1;
}

int main(){
  scanf("%d",&n),scanf("%s",s+1);
  int S = 0,T = n+2;
  scanf("%d",&m);
  for(int i = 1;i<=m;i++){
    int p;
    scanf("%s %d",t+1,&p);
    int len = strlen(t+1);
    for(int i = 1;i<=n;i++){
      if(check(i,len))
        addedge(i,i+len,1,-p);
    }
  }
  scanf("%d",&k);
  for(int i = 1;i<=n;i++){
    addedge(i,i+1,inf,0);
  }
  addedge(S,1,k,0);
  addedge(n+1,T,k,0);
  printf("%d\n",-min_cost_flow(S,T));
  return 0;
}

 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

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int MAXN = 5100,MAXM = 51000;

namespace MCMF{
  int S,T;
  struct Edge{
    int from,to;
    int cap,flow;
    int cost,nex;
  }edge[MAXM*2];
  int fir[MAXN],ecnt = 2; 
  void addedge(int a,int b,int c,int d){
    edge[ecnt] = (Edge){a,b,c,0, d,fir[a]},fir[a] = ecnt++;
    edge[ecnt] = (Edge){b,a,0,0,-d,fir[b]},fir[b] = ecnt++;
  }
  int dis[MAXN],inq[MAXN];
  bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    static queue<int> q;
    dis[S] = 0;q.push(S);
    while(!q.empty()){
      int x = q.front();q.pop();inq[x] = 0;
      for(int e = fir[x];e;e = edge[e].nex){
        int v = edge[e].to;
        if(edge[e].cap > edge[e].flow && dis[v] > dis[x] + edge[e].cost){
          dis[v] = dis[x] + edge[e].cost;
          if(!inq[v]) q.push(v),inq[v] = 1;
        }
      }
    }
    return dis[T] < dis[0];
  }
  int dfs(int x,int limit = inf){
    if(x == T || limit == 0) return limit;
    int sumf = 0;inq[x] = 1;
    for(int e = fir[x];e;e = edge[e].nex){
      int v = edge[e].to;
      if(!inq[v] && dis[v] == dis[x] + edge[e].cost){
        int f = dfs(v,min(limit,edge[e].cap - edge[e].flow));
        sumf += f,limit -= f;
        edge[e].flow += f, edge[e^1].flow -= f;
        if(limit == 0) break;
      }
    }
    return sumf;
  }
  pair<int,int> solve(int s,int t){
    S = s,T = t;
    int ansf = 0,ansc = 0;
    while(spfa()){
      int f = dfs(s);
      memset(inq,0,sizeof(inq));
      ansf += f,ansc += f * dis[t];
    }
    return make_pair(ansf,ansc);
  }
}

int n,m,s,t;

int main(){
  // scanf("%d %d %d %d",&n,&m,&s,&t);
  scanf("%d %d",&n,&m);s = 1,t = n;

  for(int i = 1;i<=m;i++){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    MCMF::addedge(a,b,c,d);
  } 
  pair<int,int> ans = MCMF::solve(s,t);
  printf("%d %d\n",ans.first,ans.second);
  return 0;
}

1
2
3
4

void reduce(int s,int t){
  for(int e = 2;e <= ecnt;e++) E0.cost += dis[E0.to] - dis[E0.from];
  delta += dis[s];
}

  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
111
112
113
114

#include <bits/stdc++.h>
#include <bits/extc++.h>
#include <unistd.h>
#define E0 edge[e]
#define E1 edge[e^1]
#define inf 0x3f3f3f3f
using namespace std;

const int MAXN = 410,MAXM = 15010;

struct Edge{
  int from,to,cap,flow,cost,nex;
}edge[MAXM*2];
int fir[MAXN],ecnt = 2;
void addedge(int a,int b,int c,int d){
  edge[ecnt] = (Edge){a,b,c,0, d,fir[a]},fir[a] = ecnt++;
  edge[ecnt] = (Edge){b,a,0,0,-d,fir[b]},fir[b] = ecnt++;
}
struct Node{
  int x,d;
  bool operator < (const Node &_n)const{return d > _n.d;}
  Node(int _x,int _d):x(_x),d(_d){}
};
// #define Node pair<int,int>
// typedef __gnu_pbds::priority_queue<Node, less<Node>, __gnu_pbds::pairing_heap_tag> heap;
// typedef priority_queue< Node ,vector< Node >,greater<Node>> heap;
typedef priority_queue<Node> heap;


int n,m;
int dis[MAXN],inq[MAXN],vis[MAXN],ansf,ansc,delta;

void reduce(int s,int t){
  for(int e = 2;e <= ecnt;e++) E0.cost += dis[E0.to] - dis[E0.from];
  delta += dis[s];
}

bool bellman(int s,int t){// t 为起点
  static queue<int> q;
  memset(dis,0x3f,sizeof(int)*(n+1));while(!q.empty()) q.pop();
  dis[t] = 0,q.push(t);inq[t] = 1;
  while(!q.empty()){
    int x = q.front();q.pop();inq[x] = 0;
    for(int e = fir[x];e;e = edge[e].nex){
      int v = E0.to,c = E1.cap,f = E1.flow,l = E1.cost;
      if(c > f && dis[v] > dis[x] + l){
        dis[v] = dis[x] + l;
        if(!inq[v]) inq[v] = 1,q.push(v);
      }
    }
  }
  return dis[s] < inf;
}

bool dijkstra(int s,int t){
  memset(dis,0x3f,sizeof(int)*(n+1));
  static heap q;
  dis[t] = 0;q.push(Node(t,0));
  while(!q.empty()){
    Node p = q.top();q.pop();int x = p.x;
    if(p.d != dis[x]) continue;
    for(int e = fir[x];e;e = edge[e].nex){
      int v = E0.to,c = E1.cap,f = E1.flow,l = E1.cost;
      if(c > f && dis[v] > dis[x] + l){
        dis[v] = dis[x] + l,q.push(Node(v,dis[v]));
      }
    }
  }
  return dis[s] < inf;
}

int dfs(int x,int t,int limit = inf){
  if(x == t || limit == 0) return limit;
  vis[x] = 1; // differ from dinic
  int sumf = 0;
  for(int &e = cur[x];e;e = edge[e].nex){
    int v = E0.to,c = E0.cap,f = E0.flow,l = E0.cost;
    if(!vis[v] && c > f && l == 0){
      int newf = dfs(v,t,min(limit,c-f));
      sumf += newf,limit -= newf;
      E0.flow += newf,E1.flow -= newf;
      if(limit == 0) break;
    }
  }
  return sumf;
}

void augment(int s,int t){
  int curf = 0;
  while(memset(vis,0,sizeof(int)*(n+1)),(curf = dfs(s,t))){
    ansf += curf,ansc += curf * delta;
  }
}

void primaldual(int s,int t){
  if(!dijkstra(s,t)) return;
  ansf = ansc = delta = 0;
  do{
    reduce(s,t),augment(s,t);
  }while(dijkstra(s,t));
}

int main(){
  scanf("%d %d",&n,&m);
  int S = 1,T = n;
  for(int i = 1;i<=m;i++){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    addedge(a,b,c,d);
  }
  primaldual(S,T);
  printf("%d %d\n",ansf,ansc);
  return 0;
}