(TIOJ) 1934 . 旅行社大特價 [最小平均值環]

https://tioj.infor.org/problems/1934

今天學到一個很酷(?)的算法，就來記錄一下惹

當初看了題解看不太懂，在網路上查到 這份資料 後，就恍然大悟惹XD。

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

typedef long long LL;
const int N = 1002;
const LL INF = (1LL<<41);
const LL INF2 = (1LL<<30);

LL adj[N][N];
LL dp[N][N];  //dp[i][j] --> from point 0 to point j threw i roads

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;n+1>=i;i++)
    {
        for (int j=0;n+1>=j;j++)
        {
            dp[i][j] = INF;
        }
    }
    for (int i=1;n>=i;i++)
    {
        for (int j=1;n>=j;j++)
        {
            scanf("%lld",&adj[i][j]);
            if (!adj[i][j]) adj[i][j] = INF;
        }
    }
    for (int i=0;n>=i;i++)
    {
        adj[0][i] = 0;
        adj[i][0] = INF;
        if (i) dp[1][i] = 0;
    }
    for (int i=2;n+1>=i;i++)
    {
        //dp[i][j] --> i roads from 0 to j
        for (int j=0;n>=j;j++)
        {
            for (int k=0;n>=k;k++)
            {
                dp[i][j] = min(dp[i][j],dp[i-1][k] + adj[k][j]);
            }
        }
    }
    LL ansup = INF2, ansdown = 1;
    for (int i=1;n>=i;i++)
    {
        //go threw all possible i's
        LL tmpup = 0,tmpdown = 1;
        if (dp[n+1][i] == INF) continue;
        for (int j=1;n>=j;j++)
        {
            if (dp[j][i] == INF) continue;
            LL up = dp[n+1][i] - dp[j][i];
            LL down = n - j + 1;
            //up/down > tmpup/tmpdown
            if (up >= 0)
            {
                if (up * tmpdown > down * tmpup)
                {
                    tmpup = up;
                    tmpdown = down;
                }
            }
        }
        if (tmpup == 0) continue;
        //ansup/ansdown > tmpup / tmpdown
        if (ansup * tmpdown > ansdown * tmpup)
        {
            ansup = tmpup;
            ansdown = tmpdown;
        }
    }
    LL gcd = __gcd(ansup,ansdown);
    ansup /= gcd;
    ansdown /= gcd;
    if (ansup == INF2) puts("-1 -1");
    else printf("%lld %lld\n",ansup,ansdown);
}

(BZOJ) 3993: [SDOI2015]星际战争

http://www.lydsy.com/JudgeOnline/problem.php?id=3993

最近真的一直在耍智障>< 一些很簡單的題目都想不太出來><

對答案作二分搜，注意到每個激光武器的攻擊量是一樣的。

所以，假設現在搜到mid，則：源點s --> 每個激光武器，流量 = t * b[i]

每個機器人 --> 匯點t，流量 = a[i]

如果激光武器 i 可以攻擊 機器人 j ，則 i-->j ，流量= a[i]

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

#define SZ(x) ((int)(x).size())

typedef long double ld;
const ld eps = 1e-9;

bool eq(ld a,ld b)
{
    return fabs(a-b) <= eps;
}

struct Dinic
{
    static const int N = 106;
    struct Edge
    {
        int to;
        ld cap;
        int rev;
        Edge(){}
        Edge(int _to,ld _cap,int _rev)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
        }
    };
    vector<Edge> G[N];
    void add_edge(int from,int to,ld cap)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to])));
        G[to].push_back(Edge(from,0,SZ(G[from])-1));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    int level[N],iter[N];
    void BFS()
    {
        memset(level,-1,sizeof(level));
        level[s]=0;
        queue<int> que;
        que.push(s);
        while (!que.empty())
        {
            int t=que.front();
            que.pop();
            for (int i=0;SZ(G[t])>i;i++)
            {
                Edge e=G[t][i];
                if (!eq(e.cap,0) && level[e.to] == -1)
                {
                    level[e.to] = level[t] +1;
                    que.push(e.to);
                }
            }
        }
    }
    ld dfs(int now, ld flow)
    {
        if (now == t) return flow;
        for (int &i=iter[now];SZ(G[now])>i;i++)
        {
            Edge &e = G[now][i];
            if (!eq(e.cap,0) && level[e.to] == level[now] + 1)
            {
                ld ret = dfs(e.to,min(flow,e.cap));
                if (!eq(ret,0))
                {
                    e.cap -= ret;
                    G[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    ld flow()
    {
        ld ret=0;
        while (true)
        {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            ld tmp=0;
            while (!eq(0, (tmp = dfs(s,1e20)) ))
            {
                ret += tmp;
            }
        }
        return ret;
    }
} kirino;

const int N = 56;

int a[N];
int b[N];
int can[N][N];

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]); //robot blood
    }
    for (int i=1;m>=i;i++)
    {
        scanf("%d",&b[i]); //weapon cost
    }
    for (int i=1;m>=i;i++)
    {
        for (int j=1;n>=j;j++)
        {
            scanf("%d",&can[i][j]);  //weapon i can beat robot j
        }
    }
    ld L=0,R=1e10;
    int cnt=100;
    int s=0,t=n+m+1;
    while (cnt--)
    {
        ld mid = (L+R)/2;
        kirino.init(t,s,t);
        for (int i=1;m>=i;i++)
        {
            kirino.add_edge(s,i,b[i]*mid);
        }
        ld tot=0;
        for (int i=1;n>=i;i++)
        {
            kirino.add_edge(i+m,t,a[i]);
            tot += a[i];
        }
        for (int i=1;m>=i;i++)
        {
            for (int j=1;n>=j;j++)
            {
                if (can[i][j])
                {
                    kirino.add_edge(i,j+m,a[j]);
                }
            }
        }
        ld ret = kirino.flow();
        if (eq(ret,tot)) R=mid;
        else L=mid;
    }
    double ans=R;
    printf("%.10f\n",ans);
}

(BZOJ) 4514: [Sdoi2016]数字配对

http://www.lydsy.com/JudgeOnline/problem.php?id=4514

先把數字分成兩類：質因數各數有奇數個的或有偶數個的

這樣一來，圖就是二分圖了。

之後再用min cost max flow亂搞即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;

#define SZ(x) ((int)(x).size())

struct Kirino
{
    static const int N = 206;
    struct Edge
    {
        LL to,cap,rev,cost;
        Edge(LL _to,LL _cap,LL _rev,LL _cost)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
            cost = _cost;
        }
    };
    vector<Edge> G[N];
    void add_edge(int from,int to,LL cap,LL cost)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to]),cost));
        G[to].push_back(Edge(from,0,SZ(G[from])-1,-cost));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    LL dis[N];
    int pre[N],pre_id[N];
    bool in_que[N];
    pii sagiri()
    {
        LL flow=0,cost=0;
        LL INF = (1LL<<40);
        while (true)
        {
            memset(in_que,0,sizeof(in_que));
            fill(dis,dis+n+1,INF);
            queue<int> que;
            que.push(s);
            dis[s]=0;
            while (!que.empty())
            {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                for (int i=0;SZ(G[t])>i;i++)
                {
                    Edge e=G[t][i];
                    if (e.cap > 0 && dis[e.to] > dis[t] + e.cost)
                    {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = i;
                        if (!in_que[e.to])
                        {
                            in_que[e.to] = 1;
                            que.push(e.to);
                        }
                    }
                }
            }
            if (dis[t] == INF) break;
            LL mn_flow = INF;
            for (int i=t;i!=s;i=pre[i])
            {
                mn_flow = min( mn_flow, G[ pre[i] ][ pre_id[i] ].cap  );
            }
            if (mn_flow*dis[t]+cost > 0)
            {
                int L=0,R=mn_flow; //L is the answer
                while (R-L != 1)
                {
                    int mid=(L+R)>>1;
                    if (mid*dis[t] + cost > 0) R=mid;
                    else L=mid;
                }
                flow += L;
                cost += L*dis[t];
                break;
            }
            flow += mn_flow;
            cost += mn_flow*dis[t];
            for (int i=t;i!=s;i=pre[i])
            {
                G[ pre[i] ][ pre_id[i] ].cap -= mn_flow;
                G[ i ][ G[ pre[i] ][ pre_id[i] ].rev ].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} meruru;

const int N = 206;

int a[N],b[N];
LL c[N];

vector<int> v[N];

vector<int> get_p(LL x)
{
    vector<int> ret;
    for (int i=2;i*i<=x;i++)
    {
        while (x%i==0)
        {
            ret.push_back(i);
            x/=i;
        }
    }
    if (x != 1) ret.push_back(x);
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    int INF = 1000000007;
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        v[i] = get_p(a[i]);
    }
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&b[i]);
    }
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&c[i]);
    }
    int s=0,t=n+1;
    meruru.init(t,s,t);
    for (int i=1;n>=i;i++)
    {
        if (SZ(v[i])%2==1)
        {
            meruru.add_edge(s,i,b[i],0);
        }
        else
        {
            meruru.add_edge(i,t,b[i],0);
        }
        for (int j=1;n>=j;j++)
        {
            if (i==j) continue;
            if (a[i]%a[j] == 0 && SZ(v[i]) - SZ(v[j]) == 1)
            {
                int ii=i,jj=j;
                if (SZ(v[ii])%2 == 0) swap(ii,jj);
                meruru.add_edge(ii,jj,INF,-c[ii]*1LL*c[jj]);
            }
        }
    }
    pii ret=meruru.sagiri();
    printf("%lld\n",ret.first);
}

(BZOJ) 1070: [SCOI2007]修车

http://www.lydsy.com/JudgeOnline/problem.php?id=1070

超神min cost max flow題。

可以想像說：假設第j個人先後修理車的順序是x_1, x_2, ......, x_t，那，a[x_1][j]的貢獻就是a[x_1][j] * t, a[x_2][j]就是a[x_2][j] * (t-1) ......

有了上面(?)的想法後，就可以寫flow了~

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

#define int long long
typedef pair<int,int> pii;

struct Flow
{
    static const int N = 100006;
    struct Edge
    {
        int to,cap,rev,cost;
        Edge(){}
        Edge(int _to,int _cap,int _rev,int _cost)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
            cost = _cost;
        }
    };
    vector<Edge> G[N];
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,int cost)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to]),cost));
        G[to].push_back(Edge(from,0,SZ(G[from])-1,-cost));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    int pre[N],pre_id[N];
    bool in_que[N];
    int dis[N];
    pii shooting_stars()
    {
        int flow=0,cost = 0;
        int INF = (1LL<<50);
        while (true)
        {
            memset(in_que,0,sizeof(in_que));
            fill(dis,dis+n+1,INF);
            queue<int> que;
            que.push(s);
            dis[s] = 0;
            while (!que.empty())
            {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                for (int i=0;G[t].size()>i;i++)
                {
                    Edge e=G[t][i];
                    if (e.cap > 0 && dis[e.to] > dis[t] + e.cost)
                    {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = i;
                        if (!in_que[e.to])
                        {
                            in_que[e.to] = 1;
                            que.push(e.to);
                        }
                    }
                }
            }
            if (dis[t] == INF) break;
            int mn_flow = INF;
            for (int i=t;i!=s;i=pre[i])
            {
                mn_flow = min( mn_flow, G[ pre[i] ][ pre_id[i] ].cap );
            }
            flow += mn_flow;
            cost += mn_flow * dis[t];
            for (int i=t;i!=s;i=pre[i])
            {
                G[ pre[i] ][ pre_id[i] ].cap -= mn_flow;
                G[ i ][ G[ pre[i] ][ pre_id[i] ].rev ].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} sagiri;

const int N = 66;

int a[N][N];

int32_t main ()
{
    int m,n;
    scanf("%lld %lld",&m,&n);
    for (int i=1;n>=i;i++)
    {
        for (int j=1;m>=j;j++)
        {
            scanf("%lld",&a[i][j]);
        }
    }
    int s=0,t = 100002;
    sagiri.init(t,s,t);
    for (int i=1;n>=i;i++)
    {
        sagiri.add_edge(i,t,1,0);
    }
    int now = n+1;
    for (int i=1;m>=i;i++)
    {
        for (int j=1;n>=j;j++)
        {
            int tmp=now;
            now++;
            sagiri.add_edge(s,tmp,1,0);
            for (int k=1;n>=k;k++)
            {
                //i-th person fix k-th car at time j
                int _=now;
                sagiri.add_edge(tmp,_,1,a[k][i]*j);
                now++;
                sagiri.add_edge(_,k,1,0);
            }
        }
    }
    pii ret = sagiri.shooting_stars();
    printf("%.2f\n",ret.second*1.0/n);
}

(BZOJ) 1061: [Noi2008]志愿者招募 [神奇的 min cost max flow ]

http://www.lydsy.com/JudgeOnline/problem.php?id=1061

直接附題解連結：http://www.cnblogs.com/jianglangcaijin/p/3799759.html

好像跟 "單純形法" 有關><。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;

struct Flow
{
    static const int N = 20006;
    struct Edge
    {
        int to,rev;
        LL cap;
        LL cost;
        Edge(int _to,LL _cap,int _rev,LL _cost)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
            cost = _cost;
        }
    };
    vector<Edge> G[N];
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,LL cap,LL cost)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to]),cost));
        G[to].push_back(Edge(from,0,SZ(G[from])-1,-cost));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    int pre[N],pre_id[N];
    LL dis[N];
    bool in_que[N];
    pii flow()
    {
        LL flow=0,cost=0;
        LL INF = (1LL << 60);
        while (true)
        {
            queue<int> que;
            memset(in_que,0,sizeof(in_que));
            fill(dis,dis+n+1,INF);
            que.push(s);
            dis[s]=0;
            while (!que.empty())
            {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                for (int id=0;G[t].size()>id;id++)
                {
                    Edge e = G[t][id];
                    if (e.cap > 0 && dis[e.to] > dis[t] + e.cost)
                    {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = id;
                        if (!in_que[e.to])
                        {
                            in_que[e.to] = 1;
                            que.push(e.to);
                        }
                    }
                }
            }
            //cout << "dis t = "<<
            if (dis[t] == INF) break;
            LL mn_flow = INF;
            for (int i=t;i!=s;i=pre[i])
            {
                mn_flow = min(mn_flow,G[ pre[i] ][ pre_id[i] ].cap);
            }
            flow += mn_flow;
            cost += mn_flow*dis[t];
            for (int i=t;i!=s;i=pre[i])
            {
                G[ pre[i] ][ pre_id[i] ].cap -= mn_flow;
                G[i][ G[ pre[i] ][ pre_id[i] ].rev ].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} solver;

LL d[10007];

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&d[i]);
    }
    int s=0,t=n+1;
    solver.init(t,s,t);
    for (int i=1;m>=i;i++)
    {
        int s,t,d;
        scanf("%d %d %d",&s,&t,&d);
        solver.add_edge(s,t+1,(1LL<<40),d);
    }
    for (int i=1;n+1>=i;i++)
    {
        LL tmp = d[i] - d[i-1];
        if (tmp >= 0) solver.add_edge(s,i,tmp,0);
        else solver.add_edge(i,t,-tmp,0);
        if (i>1) solver.add_edge(i,i-1,(1LL<<40),0);
    }
    printf("%lld\n",solver.flow().second);
}

(POJ) 1201 -- Intervals [差分約束系統]

http://poj.org/problem?id=1201

差分約束系統www。

考慮現在有很多不等式 x_i <= x_j + c ， 研究一下，會發現，這其實跟最短路徑的dis_i <= dis_j + w(i,j) 長得很像。

所以，遇到很多這種 x_i <= x_j + c的方程式，就可以使用最短路徑的建圖方法：連一條i到j的邊，邊權 = c。

那，這樣去跑最短路後，如果有遇到負環，那就代表無解。

那，如果有解的話，假設你是求從st開始求最短路徑到ed，那，dis_ed 就代表：在所有可行解中， x_ed - x_st 的最大值！

但是，這題要求的是最小的耶><。

可以先有一個小小的想法：我們可以去二分搜這個值，建一條x_st + min_dis <= x_ed 的邊。

會發現，如果是無解，那就是有負環！

那，在一點點觀察後，其實可以發現：要求x_ed - x_st  的最小值，其實就是 x_st - x_ed 的最大值，只是要取個負號XDD。

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;
const int N = 50006;
const int INF = (1<<27);

#define F first
#define S second

vector<pii> G[N];

void add_edge(int from,int to,int weight)
{
    G[from].push_back(make_pair(to,weight));
}

bool in_que[N];
int dis[N];

int spfa(int from,int to)
{
    queue<int> que;
    fill(dis,dis+N,INF);
    memset(in_que,0,sizeof(in_que));
    dis[from]=0;
    que.push(from);
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        in_que[t] = false;
        for (int i=0;G[t].size()>i;i++)
        {
            pii p=G[t][i];
            if (dis[p.F] > dis[t] + p.S)
            {
                dis[p.F] = dis[t] + p.S;
                if (!in_que[p.F])
                {
                    que.push(p.F);
                    in_que[p.F] = 1;
                }
            }
        }
    }
    return dis[to];
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        int nn=N-3;
        for (int i=0;nn>=i;i++)
        {
            G[i].clear();
        }
        int ed = 0;;
        int st = N-3;
        for (int i=1;n>=i;i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            ++x;
            ++y;
            --x;
            add_edge(y,x,-z);
            ed = max(ed,y+1);
            st = min(st,x);
            //add_edge(x,y,z);
        }
        for (int i=st+1;ed>=i;i++)
        {
            add_edge(i,i-1,0);
            add_edge(i-1,i,1);
        }
        printf("%d\n",-spfa(ed,st));
    }
}

(POI) XVIII OI Round III (finals) - day 0 (trial) Task Dynamite

https://szkopul.edu.pl/problemset/problem/Xg9hVYries5K7yMcyZYI4NLc/site/?key=statement

cool binary search + DP on tree problem

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cassert>
using namespace std;

const int N = 300006;

vector<int> G[N];

int deg[N];
int deg2[N];
int d[N];
int n,m;

int dp_mx[N],dp_mn[N];
int dp_val[N];
bool son_have_negative[N];

bool can(int t_max)
{
    queue<int> que;
    memset(son_have_negative,0,sizeof(son_have_negative));
    for (int i=1;n>=i;i++)
    {
        deg2[i] = deg[i];
        if (deg2[i] == 1)
        {
            que.push(i);
        }
    }
    memset(dp_mx,0,sizeof(dp_mx));
    memset(dp_mn,0,sizeof(dp_mn));
    int ret = 0;
    int cnt=0;
    while (!que.empty())
    {
        cnt++;
        int t=que.front();
        que.pop();
        dp_val[t] = dp_mx[t] + dp_mn[t];
        if (cnt == n && dp_val[t]>0)
        {
            ret++;
            break;
        }
        else if (cnt == n)
        {
            break;
        }
        if (dp_val[t] != 0)
        {
            if (-dp_mn[t] > dp_mx[t])
            {
                dp_val[t] = dp_mn[t];
            }
            else if (dp_mx[t] > -dp_mn[t])
            {
                dp_val[t] = dp_mx[t];
            }
            else
            {
                assert(0);
            }
        }
        if (dp_val[t] == t_max)
        {
            ret++;
            dp_val[t] = -t_max;
        }
        int update_val = dp_val[t] + ( (dp_val[t] == 0 && (d[t] == 0 || d[t] == 1 && son_have_negative[t]) )^1 );
        for (int u:G[t])
        {
            deg2[u]--;
            if (deg2[u] == 1)
            {
                que.push(u);
            }
            dp_mx[u] = max(dp_mx[u],update_val);
            dp_mn[u] = min(dp_mn[u],update_val);
            if (dp_val[t] < 0) son_have_negative[u] = 1;
        }
    }
    return ret <= m;
}

int main ()
{
    scanf("%d %d",&n,&m);
    int tot=0;
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&d[i]);
        tot += d[i];
    }
    if (tot <= m)
    {
        puts("0");
        return 0;
    }
    for (int i=1;n>i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        deg[x]++;
        deg[y]++;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int L=0,R = n+1;
    while (R-L != 1)
    {
        int mid=(L+R)>>1;
        if (can(mid)) R = mid;
        else L = mid;
    }
    printf("%d\n",R);
}