头像

mesopotamian


访客:4574

离线:18小时前



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 210, M = (10200 + N) * 2, INF = 0x3f3f3f3f;
int h[N],ecnt,A[N];
struct Edge{
    int to,nxt,f;
}e[M];
int q[N],cur[N],d[N],l[M];
int n,m,S,T;
void add(int a,int b,int c,int d)
{
    l[ecnt] = c;
    e[ecnt].to = b, e[ecnt].f = d - c, e[ecnt].nxt = h[a], h[a] = ecnt ++;
    e[ecnt].to = a, e[ecnt].f = 0, e[ecnt].nxt = h[b], h[b] = ecnt ++;
}
bool bfs()
{
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++ tt] = S; d[S] = 0; cur[S] = h[S];
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(d[to] == -1 && e[i].f)
            {
                d[to] = d[u] + 1;
                cur[to]  =h[to];
                if(to == T) return true;
                q[++ tt] = to;
            }
        }

    }
    return false;
}
int dfs(int u,int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = e[i].nxt)
    {
        cur[u] = i;
        int to = e[i].to;
        if(d[to] == d[u] + 1 && e[i].f)
        {
            int f = dfs(to, min(e[i].f,limit - flow));
            if(!f) d[to] = -1;
            e[i].f -= f, e[i ^ 1].f += f, flow += f;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = dfs(S, INF)) r += flow;
    return r;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    S = 0, T = n + 1;
    for(int i = 0; i < m; ++i )
    {
        int a, b, c, d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a, b, c, d);
        A[a] -= c; A[b] += c;
    }
    int tot = 0;
    for(int i = 1; i <= n; ++i)
        if(A[i] > 0) add(S, i , 0, A[i]), tot += A[i];
        else if(A[i] < 0) add(i, T, 0, -A[i]);
    if(tot == dinic()) 
    {
        puts("YES");
        for(int i = 0; i < m * 2; i += 2)
            printf("%d\n",l[i] + e[i ^ 1].f);
    }
    else puts("NO");
}


活动打卡代码 AcWing 2179. 圆桌问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 430, M = (150 * 270 + N) * 2, INF = 0x3f3f3f3f;

int h[N], etot, A[N];
struct Edge{
    int to,nxt,f;
}e[M];
int d[N],cur[N],q[N];
int n,m,S,T;

void add(int a,int b,int c)
{
    e[etot].to = b, e[etot].f = c, e[etot].nxt = h[a], h[a] = etot ++;
}
bool bfs(){
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++ tt] = S; d[S] = 0; cur[S] = h[S];
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(e[i].f && d[to] == -1)
            {
                d[to] = d[u] + 1;
                cur[to] = h[to];
                if(to == T) return true;
                q[++ tt] = to;

            }
        }
    }
    return false;
}
int dfs(int u,int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = e[i].nxt)
    {
        int to = e[i].to;
        cur[u] = i;
        if(d[to] == d[u] + 1 && e[i].f)
        {
            int t = dfs(to, min(limit - flow, e[i].f));
            if(!t) d[to] = -1;
            e[i].f -= t; e[i ^ 1].f += t, flow += t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = dfs(S, INF)) r += flow;
    return r;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    S = 0, T  = m + n + 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            add(i, j + n, 1), add(j + n, i, 0);

    int tot = 0;
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x; tot += x;
        add(S, i, x), add(i, S, 0);
    }
    for(int j = 1; j <= m; ++j)
    {
        int x; cin >> x;
        add(j + n, T, x); add(T, j + n, 0);
    }
    if(tot != dinic()) puts("0");
    else
    {
        puts("1");
        for(int i = 1; i <= n; ++i)
        {
            for(int j = h[i]; ~j; j = e[j].nxt)
                if(e[j].to && !e[j].f)
                    printf("%d ",e[j].to - n);
            puts("");
        }
    }
}



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e2+10, M = (N + 2) * (N * 2), INF = 0x3f3f3f3f;

int h[N], etot, A[N];
struct Edge{
    int to,nxt,f;
}e[M];
int d[N],cur[N],q[N];
int n,m,S,T;

void add(int a,int b,int c)
{
    e[etot].to = b, e[etot].f = c, e[etot].nxt = h[a], h[a] = etot ++;
}
bool bfs(){
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++ tt] = S; d[S] = 0; cur[S] = h[S];
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(e[i].f && d[to] == -1)
            {
                d[to] = d[u] + 1;
                cur[to] = h[to];
                q[++ tt] = to;
                if(to == T) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = h[u]; ~i && flow < limit; i = e[i].nxt)
    {
        int to = e[i].to;
        cur[u] = i;
        if(d[to] == d[u] + 1 && e[i].f)
        {
            int t = dfs(to, min(limit - flow, e[i].f));
            if(!t) d[to] = -1;
            e[i].f -= t; e[i ^ 1].f += t, flow += t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = dfs(S, INF)) r += flow;
    return r;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a,b;
    while(~scanf("%d%d",&a,&b))
    {
        if(a == -1 && b == -1) break;
        add(a, b, 1); add(b, a, 0);
    }
    S = 0, T = m + 1;
    for(int i = 1; i <= n; ++i) add(S,i,1), add(i, S, 0);
    for(int i = n + 1; i <=  m; ++i) add(i, T, 1), add(T,i,0);
    printf("%d\n",dinic());
    for(int i = 0; i < etot; i += 2)
    {
        if(e[i].to > n && e[i].to <= m && !e[i].f)
            printf("%d %d\n",e[i ^ 1].to, e[i].to);
    }
}



#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4+10, M = 2e5+10,INF = 0x3f3f3f3f;
int h[N],cur[N], tot,d[N],q[N],n,m,S,T;
struct Edge{
    int to,nxt,w;
}e[M];
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].w = w, e[tot].nxt = h[from];
    h[from] = tot ++;
}

bool bfs() // 分层图 可达性
{
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d); 
    q[++ tt] = S; d[S] = 0, cur[S] = h[S];
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(d[to] == -1 && e[i].w)
            {
                d[to] = d[u] + 1;   
                cur[to] = h[to];
                q[++ tt] = to;
                if(to == T) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = e[i].nxt)
    {
        cur[u] = i; // 当前弧优化
        int to = e[i].to; 
        if(d[to] == d[u] + 1 && e[i].w)
        {
            int f = dfs(to,min(limit - flow,e[i].w));
            if(!f) d[to] = -1;
            e[i].w -= f, e[i ^ 1].w += f, flow += f;
        }

    }
    return flow;
}
int dinic()
{
    int r = 0, flow;
    bfs();
    while(bfs()) while(flow = dfs(S,INF))  r += flow;
    return r;
}
int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i)
    {
        int a, b, c;
        scanf("%d%d%d",&a, &b, &c);
        add(a, b, c); add(b, a, 0);
    }
    printf("%d\n",dinic());
}


活动打卡代码 AcWing 2171. EK求最大流

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10, M = 2e4+10,INF = 0x3f3f3f3f;
int h[N], tot,d[N],vis[N],q[N],n,m,S,T,pre[N];
struct Edge{
    int to,nxt,w;
}e[M];
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].w = w, e[tot].nxt = h[from];
    h[from] = tot ++;
}

bool bfs()
{
    int hh = 0, tt = -1;
    memset(vis, 0, sizeof vis); 
    q[++ tt] = S; d[S] = INF, vis[S] = 1;
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(!vis[to] && e[i].w)
            {
                pre[to] = i;   
                vis[to] = 1;
                d[to] = min(e[i].w,d[u]);
                q[++ tt] = to;
                if(to == T) return true;
            }
        }
    }
    return false;
}
int EK()
{
    int r = 0;
    bfs();
    while(bfs())
    {
        r += d[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1].to)
            e[pre[i]].w -= d[T], e[pre[i] ^ 1].w += d[T];
    }
    return r;
}
int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i)
    {
        int a, b, c;
        scanf("%d%d%d",&a, &b, &c);
        add(a, b, c); add(b, a, 0);
    }
    printf("%d\n",EK());
}


活动打卡代码 AcWing 1082. 数字游戏

#include <iostream>
#include <vector>
using namespace std;


const int N = 35;

int f[N][N];
void init()
{
    for(int i = 0; i <= 9; ++i) f[1][i] = 1;
    for(int i = 2; i < N; ++i)
        for(int j = 0; j <= 9; ++j)
            for(int k = j; k <= 9; ++k)
                f[i][j] += f[i - 1][k];
}
int dp(int n)
{
    if(!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = 0;

    for(int i = nums.size() - 1; i >= 0; i --)
    {
        int x = nums[i];
        for(int j = last; j < x; ++j) res += f[i + 1][j];
        if(x < last) break;
        last = x;

        if(!i) res ++;
    }
    return res;
}
int main()
{
    init();
    int l,r;
    while(cin >> l >> r)
    {
        cout << dp(r) - dp(l - 1) << '\n';
    }
}


活动打卡代码 AcWing 1081. 度的数量

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int K,B;
const int N = 35;
int f[N][N];
void init(){
    for(int i = 0; i < N; ++i)
        for(int j = 0; j <= i; ++j)
        {
            if(!j) f[i][j] = 1;
            else f[i][j] = f[i-1][j] + f[i-1][j-1];
        }
}
int dp(int n)
{
    if(!n) return 0;
    vector<int> nums;
    while(n) nums.push_back(n % B), n /= B;

    int res = 0,last = 0;
    for(int i = nums.size() - 1; i >= 0; i --)
    {
        int x = nums[i];
        if(x)
        {
            res += f[i][K - last];
            if(x > 1)
            {
                res += f[i][K - last - 1];
                break;
            }
            else
            {
                last ++;
                if(last > K) break;
            }
        }
        if(!i && last == K) res ++;
    }
    return res;
}
int main()
{
    init();
    int l,r;
    cin >> l >> r >> K >> B;
    cout << dp(r) - dp(l - 1);
}


活动打卡代码 AcWing 1049. 大盗阿福

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int f[N],w[N];
int main()
{
    int T; cin >> T;
    while( T--)
    {
        memset(f, 0, sizeof f);
        int n; cin >> n;
        for(int i = 1; i <= n; ++i) scanf("%d",&w[i]);
        int ans = 0;
        int maxv = 0;
        for(int i = 1; i <= n; ++i) 
        {
            f[i] = max(f[i], maxv + w[i]); 
            maxv = max(maxv,f[i - 1]);
            ans = max(ans, f[i]);
        }
        cout << ans << '\n';

    }
}



状态机模型就不说了 主要想练习一下动态规划的思想
根据闫氏dp思想 首先划分集合. f[i] 表示必须要偷第i个商铺,那么f[i] 可以由 f[0],…f[i - 2] 转移过来
f[i] = max(f[j] + w[i]) (0 <= j < i - 1)
代码:

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int f[N],w[N];
int main()
{
    int T; cin >> T;
    while( T--)
    {
        memset(f, 0, sizeof f);
        int n; cin >> n;
        for(int i = 1; i <= n; ++i) scanf("%d",&w[i]);
        f[1] = w[1];
        int ans = f[1];
        for(int i = 2; i <= n; ++i) 
        {
            for(int j = 0; j < i - 1; ++j)
                f[i] = max(f[i], f[j] + w[i]); 
            ans = max(ans, f[i]);
        }
        cout << ans << '\n';

    }
}

然后因为n是10000 两层for循环会超时 然后想办法优化一下
我们发现f[i] 其实是由max(f[j] (0 <= j < i - 1)) 转移过来的. 然后我们类比最长上升子序列那个优化的思想,保存一下前i-1个f[j]的最大值,更新就可

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int f[N],w[N];
int main()
{
    int T; cin >> T;
    while( T--)
    {
        memset(f, 0, sizeof f);
        int n; cin >> n;
        for(int i = 1; i <= n; ++i) scanf("%d",&w[i]);
        f[1] = w[1];
        int ans = f[1];
        int maxv = w[0];
        for(int i = 2; i <= n; ++i) 
        {
            f[i] = max(f[i], maxv + w[i]); 
            maxv = max(maxv,f[i - 1]);
            ans = max(ans, f[i]);
        }
        cout << ans << '\n';

    }
}


活动打卡代码 AcWing 1015. 摘花生

mesopotamian
1个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2+10;
int a[N][N];
int main()
{
    int T; cin >> T;
    while(T--)
    {
        int n,m; cin >> n >> m;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                cin >> a[i][j],a[i][j]+=max(a[i-1][j],a[i][j-1]);
        cout << a[n][m] << "\n";
    }
}