(Sky OJ) 154. DAY 4 PH. 字串雜湊

https://pc2.tfcis.org/sky/index.php/problem/view/154/

很奇怪的min cut XD

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

typedef long long LL;

struct Dinic {
    static const int MAX_N = 4e4 + 6;
    struct Edge {
        LL to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    int n,s,t;
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n+1>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N],level[MAX_N];
    void BFS() {
        queue<int> que;
        memset(level,-1,sizeof(level));
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (Edge &e:edg[t]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[t] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    LL dfs(int id,LL flow) {
        if (id == t) return flow;
        for (int &i=iter[id];SZ(edg[id])>i;i++) {
            Edge &e=edg[id][i];
            if (e.cap > 0 && level[e.to] == level[id] + 1) {
                int ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const LL INF = 1e15 + 7;
    LL flow() {
        LL ret=0;
        while (1) {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            LL tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

typedef long long LL;
typedef vector<LL> vint;
const int MAX_N = 106;
const LL mod = 71234;
const LL INF = 1e9 +7;
int v[144];

vint dp[MAX_N];
vint mn[MAX_N];
vint edg[MAX_N];
int deg[MAX_N];
bool visit[MAX_N];
#define SZ(x) ((int)(x).size())
vint dp2[MAX_N];
int ppre[MAX_N];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >>n >>m;
    for (int i='a';'z'>=i;i++) {
        cin >>v[i];
    }
    for (int i=1;n>=i;i++) {
        dp[i].push_back(INF);
        string s;
        cin >> s;
        LL pre=0;
        int sz=0;
        for (int j=0;s.size()>j;j++) {
            pre *= (j);
            pre += v[s[j]];
            pre %= mod;
            if (SZ(s) % (j+1) == 0) {
                dp[i].push_back(pre);
                sz++;
            }
        }
        ppre[i] = ppre[i-1] + sz;
    }
    int s=0,t=ppre[n] + 1;
    dinic.init(t,s,t);
    for (int i=1;n>=i;i++) {
        int first=ppre[i-1];
        dinic.add_edge(s,first+1,INF);
        for (int j=1;SZ(dp[i])>j;j++) {
            if (j==SZ(dp[i]) - 1) dinic.add_edge(first+j,t,dp[i][j]);
            else dinic.add_edge(first+j,first+j+1,dp[i][j]);
        }
    }
    for (int i=1;m>=i;i++) {
        int x,y;
        cin >> x >> y;
        int firstx=ppre[x-1],firsty=ppre[y-1];
        for (int j=1;min(SZ(dp[x]),SZ(dp[y])) > j;j++) {
            dinic.add_edge(firstx+j,firsty+j,INF);
        }
    }
    cout<<dinic.flow()<<'\n';
}