下雪了

洛谷 P3381 最小费用最大流(网络流/最小费用最大流/Dinic + SFPA)

如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。

输入格式

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi),单位流量的费用为fi。

输出格式

一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。

输入输出样例

输入 #1

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

输出 #1

50 280

说明/提示

时空限制:1000ms,128M

(BYX:最后两个点改成了1200ms)

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=1000,M<=1000

对于100%的数据:N<=5000,M<=50000

样例说明:

如图,最优方案如下:

第一条流为4–>3,流量为20,费用为3*20=60。

第二条流为4–>2–>3,流量为20,费用为(2+1)*20=60。

第三条流为4–>2–>1–>3,流量为10,费用为(2+9+5)*10=160。

故最大流量为50,在此状况下最小费用为60+60+160=280。

故输出50 280。

思路:初学费用流,找到了一篇不错的教程,思路是利用最短路保证最小费用,再在最大流的基础上,算出最大流的最小的费用,似乎可以把sfpa换成dijkstra?

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int to;//指向
    int f;//流量
    int w;//单位花费
    int rev;//反向边序号
    unit() {};
    unit(int n, int ff, int ww, int r) :to(n), f(ff), w(ww), rev(r) {};
};
vector<unit> G[50001];
int cur[50001];
int dis[50001];
bool v[50001];

int n, m, st, ed;
int maxflow, mincost;

void add(int x, int y, int f, int w)//建边
{
    G[x].push_back(unit(y, f, w, G[y].size()));
    G[y].push_back(unit(x, 0, -w, G[x].size() - 1));//反向边,流量为0,单位花费为负
}

bool spfa()//标准SPFA
{
    ffor(i, 1, n)
    {
        v[i] = false;
        dis[i] = IMAX;
    }
    dis[st] = 0;
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        v[f] = false;
        for (vector<unit>::iterator it = G[f].begin(); it != G[f].end(); it++)
        {
            unit u = *it;
            if (u.f && dis[f] + u.w < dis[u.to])
            {
                dis[u.to] = dis[f] + u.w;
                if (!v[u.to])
                {
                    q.push(u.to);
                    v[u.to] = true;
                }
            }
        }
    }
    return dis[ed] != IMAX;//能走到就返回
}

int dfs(int x, int f)
{
    if (x == ed)
        return f;
    v[x] = true;//防止重复走
    int sum = 0;
    for (int& i = cur[x]; i <= G[x].size() - 1; i++)
    {
        unit& u = G[x][i];
        if (!v[u.to] && u.f && dis[u.to] == dis[x] + u.w)
        {
            int flow = dfs(u.to, min(f - sum, u.f));
            if (flow)//确认可以流通,就对边进行操作,记录最大流和最小花费
            {
                sum += flow;
                u.f -= flow;
                G[u.to][u.rev].f += flow;
                mincost += u.w * flow;
                if (sum == f)break;
            }
        }
    }
    v[x] = false;
    return sum;
}
void dinic()
{
    while (spfa())
    {
        mes(cur, 0);
        maxflow += dfs(st, IMAX);
    }
}

signed main()
{
    cin >> n >> m >> st >> ed;
    maxflow = mincost = 0;
    ffor(i, 1, m)
    {
        int x, y, w, c;
        scanf("%lld%lld%lld%lld", &x, &y, &w, &c);
        add(x, y, w, c);
    }
    dinic();
    printf("%lld %lld\n", maxflow, mincost);
}

 

POJ – 1797 Heavy Transportation (最短路/Dijkstra模板)

模板题emmm

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

int mp[1001][1001];
bool v[1001];
int dis[1001];
int n;

void dj(int x)
{
    mes(v, 0);
    v[x] = true;
    ffor(i, 1, n) dis[i] = mp[x][i];
    int pos;
    ffor(x, 1, n - 1)
    {
        int m = 0;
        ffor(i, 1, n)
        {
            if (!v[i] && dis[i] > m)
            {
                pos = i;
                m = dis[i];
            }
        }
        v[pos] = true;
        ffor(i, 1, n)
            if (!v[i])
                dis[i] = max(dis[i], min(dis[pos], mp[pos][i]));
    }
}

signed main()
{
    int T;
    while (cin >> T)
    {
        ffor(t, 1, T)
        {
            int m;
            scanf("%lld%lld", &n, &m);
            ffor(i, 1, n)
            {
                ffor(k, i + 1, n)
                    mp[i][k] = mp[k][i] = 0;
            }
            while (m--)
            {
                int a, b, c;
                scanf("%lld%lld%lld", &a, &b, &c);
                mp[a][b] = mp[b][a] = max(mp[a][b], c);
            }
            dj(1);
            cout << "Scenario #" << t << ":" << endl << dis[n] << endl << endl;
        }
    }
}

 

Kattis secretchamber – Secret Chamber at Mount Rushmore(弗洛伊德求闭包/弗洛伊德模板)

WF的题,放弃好了。

emmm,一开始是想用字典树什么的,就没去看。后来发现,我们要把一个点与另一个点连起来,那就想到如果把它们看成26*26的图,说不定就好了呢?题目范围给的很小,那么n^3是绝对不会超时的,所以就用Floyd来做,果然不出所料。

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

int mp[30][30];

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        getchar();
        ffor(i, 0, 26)
        {
            ffor(k, 0, 26)
                mp[i][k] = 99;
            mp[i][i] = 0;
        }
        ffor(i, 1, n)
        {
            char x, y;
            scanf("%c %c%*c", &x, &y);
            mp[x - 'a'][y - 'a'] = 0;
        }
        ffor(j, 0, 26)
        {
            ffor(i, 0, 26)
            {
                ffor(k, 0, 26)
                    mp[i][k] = min(mp[i][k], mp[i][j] + mp[j][k]);
            }
        }
        ffor(i, 1, m)
        {
            char s1[60], s2[60];
            cin >> s1 >> s2;
            int l1 = strlen(s1);
            int l2 = strlen(s2);
            bool ok = true;
            if (l1 == l2)
            {
                ffor(i, 0, l1 - 1)
                {
                    int x = s1[i] - 'a';
                    int y = s2[i] - 'a';
                    if (mp[x][y] != 0)
                    {
                        ok = false;
                        break;
                    }
                }
            }
            else ok = false;
            if (ok) cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }
}

 

HDU1166 – 敌兵布阵(线段树模板)

重新写了一发模板(乖乖地push_up和push_down了……)

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int l;
    int r;
    int sum;
    int lazy;
};

unit tab[50005 << 2];
int num[50005];
int rt;
int cnt;

void pushdown(int x,int l,int r)
{
    if (tab[x].lazy)
    {
        tab[tab[x].l].lazy += tab[x].lazy;
        tab[tab[x].r].lazy += tab[x].lazy;
        tab[tab[x].l].sum += tab[x].lazy * (r - l + 1);//要看情况乘多少,例如取min的话只乘1,总和就要乘上区间长度
        tab[tab[x].r].sum += tab[x].lazy * (r - l + 1);
        tab[x].lazy = 0;
    }
}

void pushup(int x)
{
    tab[x].sum = tab[tab[x].l].sum + tab[tab[x].r].sum;
}

void build(int& x, int l, int r)
{
    x = ++cnt;
    tab[x].lazy = 0;
    if (l == r)
    {
        tab[x].sum = num[l];
        return;
    }
    int m = (l + r) >> 1;
    build(tab[x].l, l, m);
    build(tab[x].r, m + 1, r);
    pushup(x);
}

void update(int x, int L, int R, int l, int r,int value)
{
    if (L <= l && R >= r)
    {
        tab[x].sum += value * (r - l + 1);
        tab[x].lazy += value;
        return;
    }
    pushdown(x, l, r);
    int m = (l + r) >> 1;
    if (L <= m) update(tab[x].l, L, R, l, m, value);
    if (R > m) update(tab[x].r, L, R, m + 1, r, value);
    pushup(x);
}

int check(int x, int L, int R, int l, int r)
{
    if (L <= l && R >= r)
        return tab[x].sum;
    pushdown(x, l, r);
    int m = (l + r) >> 1;
    int sum = 0;
    if (L <= m) sum += check(tab[x].l, L, R, l, m);
    if (R > m) sum += check(tab[x].r, L, R, m + 1, r);
    pushup(x);
    return sum;
}


signed main()
{
    int T;
    cin >> T;
    ffor(c, 1, T)
    {
        cnt = 0;
        int n;
        cin >> n;
        ffor(i, 1, n)
            scanf("%lld", &num[i]);
        build(rt, 1, n);
        printf("Case %lld:\n", c);
        while (true)
        {
            char s[10];
            int x, y;
            scanf("%s", s);
            if (s[0] != 'E')
            {
                scanf("%lld%lld", &x, &y);
                if (s[0] == 'A')
                    update(rt, x, x, 1, n, y);
                else if (s[0] == 'S')
                    update(rt, x, x, 1, n, -y);
                else if (s[0] == 'Q')
                    printf("%lld\n", check(rt, x, y, 1, n));
            }
            else break;
        }
    }
    return 0;
}

 

洛谷P3384 – 树链剖分(模板)

树链剖分模板题emmm

(又因为int什么的wa了啊….以后#define int long long 好了……)

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(int i = a; i <= b; i++)
#define rfor(i, a, b) for(int i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int l;
    int r;
    ll sum;
    ll lazy;
};
unit tab[100005<<2];

vector<int> G[100005];
int fa[100005];
int dep[100005];
int sz[100005];
int rk[100005];
int id[100005];
int top[100005];
int son[100005];
int w[100005];

int n, q, rt, root;
int cnt;

void dfs1(int x, int f, int d)//处理出fa、dep
{
    dep[x] = d;
    fa[x] = f;
    sz[x] = 1;
    int maxson = -1;
    for (auto i : G[x])
    {
        if (i == f)continue;
        dfs1(i, x, d + 1);
        sz[x] += sz[i];
        if (sz[i] > maxson)
        {
            son[x] = i;
            maxson = sz[i];
        }
    }
}

void dfs2(int x, int t)//处理出rk、top、id
{
    id[x] = ++cnt;
    rk[cnt] = w[x];
    top[x] = t;
    if (!son[x])
        return;
    dfs2(son[x], t);
    for (auto i:G[x]) 
    {
        if (i != fa[x] && i != son[x])
            dfs2(i, i);
    }
}

void build(int &x,int l,int r)
{
    x = ++cnt;
    tab[x].lazy = 0;
    if (l == r)
    {
        tab[x].sum = rk[l] % mod;
        return;
    }
    int m = (l + r) >> 1;
    build(tab[x].l, l, m);
    build(tab[x].r, m + 1, r);
    tab[x].sum = (tab[tab[x].l].sum + tab[tab[x].r].sum) % mod;
}

void update(int x, int L, int R, int l, int r, ll value)// 汇总子节点的时候,要注意加上自己的lazy
{
    if (L <= l && R >= r)
    {
        tab[x].sum = (tab[x].sum + (r - l + 1) * value) % mod;
        tab[x].lazy += value;
        return;
    }
    int m = (l + r) >> 1;
    if (L <= m) update(tab[x].l, L, R, l, m, value);
    if (R > m) update(tab[x].r, L, R, m + 1, r, value);
    tab[x].sum = (tab[tab[x].l].sum + tab[tab[x].r].sum%mod + (tab[x].lazy * (r - l + 1))%mod) % mod;
}

ll check(int x, int L, int R, int l, int r, ll add)// 用add把每一层的lazy相加(*很重要!*)
{
    if (L <= l && R >= r)
        return (tab[x].sum + add * (r - l + 1)) % mod;
    int m = (l + r) >> 1;
    ll sum = 0;
    if (L <= m) sum = (sum + check(tab[x].l, L, R, l, m, (add + tab[x].lazy)%mod)) % mod;
    if (R > m) sum = (sum + check(tab[x].r, L, R, m + 1, r, (add + tab[x].lazy)%mod)) % mod;
    return sum;
}

void lpls(int x,int y,int z)
{
    z %= mod;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        update(rt, id[top[x]], id[x], 1, n, z);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    update(rt, id[x], id[y], 1, n, z);
}

ll lcheck(int x, int y)
{
    ll res = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        res = (res + check(rt, id[top[x]], id[x], 1, n, 0)) % mod;
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    res = (res + check(rt, id[x], id[y], 1, n, 0)) % mod;
    return res;
}

void spls(int x, int y)
{
    update(rt, id[x], id[x] + sz[x] - 1, 1, n, y);
}

ll scheck(int x)
{
    return check(rt, id[x], id[x]+sz[x]-1, 1, n, 0) % mod;
}

signed main()
{
    cin >> n >> q >> root >> mod;
    ffor(i, 1, n)
        scanf("%lld", &w[i]);
    ffor(i, 1, n - 1)
    {
        int x, y;
        scanf("%lld%lld", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cnt = 0;
    dfs1(root, 0, 1);
    dfs2(root, root);
    cnt = 0;
    build(rt, 1, n);
    ffor(i, 1, q)
    {
        int o;
        scanf("%lld", &o);
        int x, y, z;
        switch (o)
        {
        case 1:
            scanf("%lld%lld%lld", &x, &y, &z);
            lpls(x, y, z);
            break;
        case 2:
            scanf("%lld%lld", &x, &y);
            printf("%lld\n",lcheck(x, y));
            break;
        case 3:
            scanf("%lld%lld", &x, &y);
            spls(x, y);
            break;
        default:
            scanf("%lld", &x);
            printf("%lld\n", scheck(x));
            break;
        }
    }
    return 0;
}