devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

人类悲欢，各不相同_悲观各不相同

作者：盐析白兔 | 2024-08-08 12:44:34

赞

踩

悲观各不相同

在这里插入图片描述
在这里插入图片描述
太扎心了《所以还是继续学习Acm吧》 (￢︿̫̿￢☆) 坏女人zyx

先说说昨天(27号)的牛客多校B题吧，我啥都没打，开局三小时了来看看数学题，就猜了个结论 AC了 ，计算F(n)=F(n-1)*2n -1/2n 求逆元
显然猜的这个式子还是很简单的，但是在2e7的数据下你只能O(n)预处理O(1)查询，所以求逆元递推到2e7这个范围，我们不能用递归求逆元要线性求逆元，那么线性求2n 的逆元 也就是每次累乘 1/2 的逆元取模 - - 然后就愉快AC了 （显然我不知道正解为什么是这个公式，猜的，所以我还是大水逼） Binary Vector

#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
//#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;
const int ma=2e7+3;
ll ff[ma];
ll res[ma];
void oppp(){
 ll p=mods;//
ff[1]=500000004;
res[1]=2;
ll inv=ff[1];
for(int i=2;i<=ma;i++){
res[i]=res[i-1]*2%p;
inv=inv*ff[1]%p;
ff[i]=(ff[i-1]*(res[i]-1+p)%p*inv+p)%p;
}
for(int i=2;i<=ma;i++){
    ff[i]=ff[i]^ff[i-1];
}
}
signed main(){
ll t;
read(t);
oppp();
while(t--){
 ll op;
 read(op);
 printf("%d\n",ff[op]);
}
}
好了开始今日的学习吧，啥也不会的大彩笔    


  • 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

拉格朗日插值&&懵逼到懵懂
先来一个例题 CF &&math 2600
给你一个n和一个k 求 Σ ik i 从1到n 结果对1e9+7取模
显然可以用k+1次的多项式表达出来 又因为此处所取的点是连续的
所以可以得 在这里插入图片描述
上下化简 这里有个小技巧，给分子多乘一个n-i 然后对于分母多做一次n-i的逆元运算 哎， 自闭了，这个定理 （配图的ik 指的是前缀ik）

#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;

ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p)
{
    a%=p;
    b%=p;
    ll r=0,v=a;
    while(b)
    {
        if(b&1)
        {
            r=(r+v)%p;

               r=(r+p)%p;
        }
        v<<=1;
        v=(v+p)%p;
        b>>=1;
    }
    return r%p;
}
ll pow_mod(ll x,ll n,ll mod)
{
    ll res=1;
    while(n)
    {
        if(n&1)
        res=mult(res,x,mod);
        x=mult(x,x,mod);
        n>>=1;
    }
    return res;
}
ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;}
bool Miller_Rabin(ll n)
{if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}
srand(time(NULL));ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if (!b){
        x=1,y=0;
        return a;
    }
    ll ans=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return ans;
}
ll INV(ll a,ll b){ll x,y;return exgcd(a,b,x,y),(x%b+b)%b;}
ll crt(ll x,ll p,ll mod){return INV(p/mod,mod)*(p/mod)*x;}
ll FAC(ll x,ll a,ll b)
{if(!x)return 1;ll ans=1;for(ll i=1;i<=b;i++)if(i%a)ans*=i,ans%=b;
ans=pow_mod(ans,x/b,b);for(ll i=1;i<=x%b;i++)if(i%a)ans*=i,ans%=b;return ans*FAC(x/a,a,b)%b;}
ll C(ll n,ll m,ll a,ll b)
{ll N=FAC(n,a,b),M=FAC(m,a,b),Z=FAC(n-m,a,b),sum=0,i;for(i=n;i;i=i/a)sum+=i/a;
for(i=m;i;i=i/a)sum-=i/a;for(i=n-m;i;i=i/a)sum-=i/a;return N*pow_mod(a,sum,b)%b*INV(M,b)%b*INV(Z,b)%b;}
ll exlucas(ll n,ll m,ll p)
{ll t=p,ans=0,i;for(i=2;i*i<=p;i++){ll k=1;while(t%i==0){k*=i,t/=i;}
ans+=crt(C(n,m,i,k),p,k),ans%=p;}if(t>1)ans+=crt(C(n,m,t,t),p,t),ans%=p;return ans % p;}
ll H(ll x,ll p)  //错排
{
       ll ans=0;
    if(x==0)return 1;
    x=x%(2*p);
    if(x==0)x=2*p;
    for(int i=2;i<=x;++i)
    ans=(ans*i+(i%2==0?1:-1))%p;
    return (ans+p)%p;
}
const int ma=1e6+7;
ll pre[ma]; //前缀
ll inv[ma]; // 后缀
ll sub;
ll k,n;
ll fa[ma];
//ll pren[ma];
void check(){
sub=1;
fa[0]=1;
inv[0]=1;
for(int i=1;i<=k+2;i++){
  pre[i]=(pre[i-1]+qp(i,k,mods))%mods;   //自然数幂次
  //前缀阶乘
    fa[i]=(fa[i-1]*i)%mods;  //阶乘
   sub=sub*(n-i)%mods;
}


inv[k+2]=qpn(fa[k+2],mods-2,mods);
for(int i=k+1;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mods;
 // n-1*n-2*n-3
}

}
signed main(){

read(n);
read(k);
if(n<=k+2){
ll add=0;
for(int i=1;i<=k+2;i++){
 add=(add+qp(i,k,mods))%mods;
if(i==n){
  printf("%lld\n",add%mods);
return 0;
}
}

}
check(); //  预处理
ll ans=0;
for(int i=1;i<=k+2;i++){
   ans+=pre[i]*sub%mods*qpn(n-i,mods-2,mods)%mods*inv[i-1]%mods*inv[k+2-i]%mods*((k+2-i)%2==0?1:-1)%mods;ans=ans%mods;

}
printf("%lld\n",(ans+mods)%mods);
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
  • 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
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151

网络流24题&&魔术球
其实要把问题转化，用多少个球可以把N个柱子覆盖 也就是最小路径覆盖问题，枚举球的数量 每次往残量网络里面继续跑Dinic 就OK直到maxflow>=n
然后输出路径 （这一点要是想不到的话直接等死）

#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
struct edge {
    int to, cap;
} e[2000006];
vector<int> g[N];
int EN, NN, S, T, dep[N], pre[N], num[N], cur[N];
// EN边数 NN点数 S源点 T汇点
void bfs() {
    for (int i = 1; i <= NN; i++) dep[i] = NN;
    dep[T] = 0;
    queue<int> q;
    q.push(T);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i : g[u])
            if (dep[e[i].to] == NN && e[i ^ 1].cap > 0) {
                dep[e[i].to] = dep[u] + 1;
                q.push(e[i].to);
            }
    }
}
int augment() {
    int mf = 0x3f3f3f3f;
    for (int u = T; u != S; u = e[pre[u] ^ 1].to) mf = min(mf, e[pre[u]].cap);
    for (int u = T; u != S; u = e[pre[u] ^ 1].to) e[pre[u]].cap -= mf, e[pre[u] ^ 1].cap += mf;
    return mf;
}
int maxflow() {
    for (int i = 1; i <= NN; i++) {
        pre[i] = 0;
        num[i] = 0;
        cur[i] = 0;
    }
    bfs();
    int u = S, ans = 0;
    for (int i = 1; i <= NN; i++) num[dep[i]]++;
    while (dep[S] < NN) {
        if (u == T)
            ans += augment(), u = S;
        bool nxt = 0;
        for (int &i = cur[u]; i < g[u].size(); i++) {
            int j = g[u][i];
            if (e[j].cap > 0 && dep[e[j].to] == dep[u] - 1) {
                pre[u = e[j].to] = j;
                nxt = 1;
                break;
            }
        }
        if (nxt == 0) {
            int md = NN - 1;
            for (int i : g[u])
                if (e[i].cap)
                    md = min(md, dep[e[i].to]);
            if (--num[dep[u]] == 0)
                break;
            num[dep[u] = md + 1]++;
            cur[u] = 0;
            if (u != S)
                u = e[pre[u] ^ 1].to;
        }
    }
    return ans;
}
void addedge(int u, int v, int w) {
    g[u].push_back(EN);
    e[EN++] = edge{ v, w };
    g[v].push_back(EN);
    e[EN++] = edge{ u, 0 };
}
int pren[N], nxtn[N];
int main() {
    int n;
    cin >> n;
    S = 4001, T = 4002, NN = 4002;
    for (int i = 1; i <= 2000; i++) {
        addedge(S, i, 1);
        addedge(i + 2000, T, 1);
    }
    int ans = 0, flow = 0;
    for (int i = 1; i <= 2000; i++) {
        for (int j = 1; j < i; j++)
            if ((int)sqrt(i + j) * (int)sqrt(i + j) == i + j)
                addedge(j, i + 2000, 1);
        flow += maxflow();
        int cnt = i - flow;

        if (cnt <= n) {
            ans = i;
            memset(pren, 0, sizeof pren);
            memset(nxtn, 0, sizeof nxtn);
            for (int j = 1; j <= i; j++)
                for (int k : g[j])
                    if (e[k].to != S && e[k].cap == 0) {
                        pren[e[k].to - 2000] = j;
                        nxtn[j] = e[k].to - 2000;
                    }
        }
    }
    cout << ans << endl;

    for (int i = 1; i <= n; i++)
        if (pren[i] == 0) {
            int now = i;
            cout << now;
            while (now = nxtn[now]) cout << ' ' << now;
            cout << endl;
        }
    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
  • 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

网络流24题&&圆桌聚餐
有多个公司，每个公司又有多个人，然后此处又有多个桌子可以容纳下多个人，要求尽量使得不同公司的人在一桌交流 ，输出每个桌子的坐人情况，如果无解就输出0
先捋一捋这个模型怎么建立， 显然公司可以连接到源点S 边容为人数
那么我们就可以把桌子链接汇点 边容为桌子可以坐的人数 然后把每个公司像每个桌子都拉一条边容为1的，就可以保证 尽量使得不同公司的人在同一个桌子交流 ，然后我们跑Dinic最大流，如果流量比总人数小，那么肯定无解，否则 我们遍历路径 输出它，从公司为起点遍历，边是主边，那么只要下标是奇数而且folw为0了 就是可行的路径 标记号了再输出，这个题有点卡输出格式

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
ll gcd(ll a, ll b) {
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 5 * 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N], zhanv;
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void in(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                         // bfs求源点到所有点的最短路
    for (Re i = 0; i <= n + m + 1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}
const int ma = 300;
ll pep[ma * 2];
ll cu[ma * 2];
ll rnm[ma * 2];
ll cnm = 0;
void cle() {
    memset(head, 0, sizeof(head));
    maxflow = 0;
    o = 1;
}
signed main() {
    while (scanf("%lld%lld", &m, &n) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        ll sum = 0;
        cle();
        for (int i = 1; i <= m; i++) {
            read(pep[i]);
            sum = sum + pep[i];
        }
        for (int i = 1; i <= n; i++) {
            read(cu[i]);
        }
        for (int i = 1; i <= m; i++) {
            add(0, i, pep[i]);
            add(i, 0, 0);
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                add(i, j + m, 1);
                add(j + m, i, 0);
            }
        }
        for (int j = 1; j <= n; j++) {
            add(j + m, n + m + 1, cu[j]);
            add(n + m + 1, j + m, 0);
        }
        st = 0;
        ed = n + m + 1;
        Dinic(st, ed);
        // printf("%lld\n",maxflow);
        if (maxflow < sum) {
            printf("0\n");
        } else {
            printf("1\n");
            for (int i = 1; i <= m; i++) {
                for (int j = head[i]; j != 0; j = a[j].next) {
                    if (a[j].flow == 0 && !(j & 1)) {
                        // printf("%lld ",a[j].to-m);
                        rnm[++cnm] = a[j].to - m;
                    }
                }
                for (int op = cnm; op >= 1; op--) {
                    printf("%lld", rnm[op]);
                    if (op != 1) {
                        printf(" ");
                    }
                }
                cnm = 0;
                memset(rnm, 0, sizeof(rnm));
                printf("\n");
            }
        }
    }
    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
  • 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
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165

网络流24题&&试题库
emm 题面自己读读吧，K种题型，题库有N个题，一个题可能具有多个属性(题型) 现在要从中抽取m个题 （m☞的是K种题型 需求量的总和）要求包含所有类型的题 问怎么抽 无解就输出no anwer 对于N，每行先输入一个P代表它有P种题目类型， 然后输入具体类型
首先要想想这个题库的题 和我们要抽的题目有啥关系， 其实是没啥关系的
主要的落脚点在于 满足K种类型的题 而且数量恰好是M 显然我们要把题目种类建立在汇点边容为需求量，那么对于每个题我们就要把它建立在源点， 题与题型之间建立边容为1

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
ll gcd(ll a, ll b) {
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 5 * 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N], zhanv;

ll k;
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void in(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                         // bfs求源点到所有点的最短路
    for (Re i = 0; i <= n + k + 1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}
const int ma = 3000;
ll pep[ma * 2];
ll cu[ma * 2];
ll rnm[ma * 2];
ll cnm = 0;
void cle() {
    memset(head, 0, sizeof(head));
    maxflow = 0;
    o = 1;
}
signed main() {
    while (scanf("%lld%lld", &k, &n) != EOF) {
        ll sum = 0;
        cle();
        for (int i = 1; i <= k; i++) {
            ll cf;
            read(cf);  //第i个类型的题数需要
            add(n + i, n + 1 + k, cf);
            add(n + 1 + k, n + i, 0);
            sum = sum + cf;  //总数
        }

        for (int i = 1; i <= n; i++) {
            ll tt;
            read(tt);
            add(0, i, 1);
            add(i, 0, 0);  //题  源点
            while (tt--) {
                ll co;
                read(co);  //类型
                add(i, co + n, 1);
                add(co + n, i, 0);
            }
        }

        st = 0;
        ed = n + k + 1;
        Dinic(st, ed);
        // printf("%lld\n",maxflow);
        if (maxflow != sum) {
            printf("No Solution!\n");
            continue;
        }

        else {
            for (int i = 1 + n; i <= k + n; i++) {
                printf("%lld: ", i - n);
                for (int j = head[i]; j != 0; j = a[j].next) {
                    if (a[j].to <= n && a[j].flow) {
                        // printf("%lld ",a[j].to);
                        rnm[++cnm] = a[j].to;
                    }
                }  // printf("Q \n");

                for (int op = cnm; op >= 1; op--) {
                    printf("%lld", rnm[op]);
                    if (op != 1) {
                        printf(" ");
                    }
                }
                printf("\n");
                cnm = 0;
                memset(rnm, 0, sizeof(rnm));
            }
        }
    }
    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
  • 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
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168

网络流24题&&方格取数
N*M的方格 每个格子有个点权，要我们取数 ，使得和最大，取的数边不能香蕉，问最大的和是多少 首先不妨想想这种边不相交的限制，想想一个黑白棋盘，就很直观了。那么我们让黑色方格链接源点 白色格子链接汇点，又因为这种矛盾关系，我们利用最大独立集来解决
在这里插入图片描述

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
ll gcd(ll a, ll b) {
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 5 * 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N], zhanv;

ll k;
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void in(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                         // bfs求源点到所有点的最短路
    for (Re i = 0; i <= n * m + 1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}
const int ma = 3000;
ll pep[ma * 2];
ll cu[ma * 2];
ll rnm[ma * 2];
ll cnm = 0;

ll e[50][50];
void cle() {
    memset(head, 0, sizeof(head));
    maxflow = 0;
    memset(e, 0, sizeof(e));
    o = 1;
}
signed main() {
    while (scanf("%lld%lld", &n, &m) != EOF) {
        ll ans = 0;
        cle();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                read(e[i][j]);
                ans = ans + e[i][j];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if ((i + j) % 2 == 1) {
                    add(0, (i - 1) * m + j, e[i][j]);
                    add((i - 1) * m + j, 0, 0);  //黑点染色
                    if (i - 2 >= 0) {
                        //上
                        add((i - 1) * m + j, (i - 2) * m + j, inf);
                        add((i - 2) * m + j, (i - 1) * m + j, 0);
                    }
                    if (i <= n - 1) {
                        //下
                        add((i - 1) * m + j, i * m + j, inf);
                        add(i * m + j, (i - 1) * m + j, 0);
                    }

                    if (j + 1 <= m) {
                        add((i - 1) * m + j, (i - 1) * m + j + 1, inf);
                        add((i - 1) * m + j + 1, (i - 1) * m + j, 0);

                        //右边
                    }

                    if (j - 1 >= 1) {  //左边
                        add((i - 1) * m + j, (i - 1) * m + j - 1, inf);
                        add((i - 1) * m + j - 1, (i - 1) * m + j, 0);
                    }

                }

                else {
                    add((i - 1) * m + j, n * m + 1, e[i][j]);
                    add(n * m + 1, (i - 1) * m + j, 0);
                }
            }
        }
        st = 0;
        ed = n * m + 1;
        Dinic(st, ed);
        printf("%lld\n", ans - maxflow);
    }
    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
  • 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
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167

网络流24题&&思维建图&&最大流
拆点，X与Y集合 分别连接源点汇点 边容为Ri 如果要买入餐巾，那么对于每个Y 从源点拉一条边容为inf 费用为P的边， 同理洗餐巾从X集合拉到对应天数的Y集合去 连上花费 注意我们可以把今天的餐巾放在明天处理（延期处理） 所以建图就很直观了

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
//#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
const int N = 5 * 1e5, M = 2 * 1e6 + 3, inf = 2e9;
int x, y, z, w, o = 1, n, m, h, t, st, ed, cyf[N], pan[N], pre[N], dis[N], head[N];
ll mincost, maxflow;
struct QAQ {
    int w, to, next, flow;
} a[M << 1];
queue<int> Q;
inline void read(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z, Re w) {
    a[++o].flow = z, a[o].w = w, a[o].to = y, a[o].next = head[x], head[x] = o;
}
inline void add_(Re a, Re b, Re flow, Re w) { add(a, b, flow, w), add(b, a, 0, -w); }
inline int SPFA(Re st, Re ed) {
    for (Re i = 0; i <= n * 2 + 1; ++i) dis[i] = inf, pan[i] = 0;  //有多少个点就初始化到那个地方去
    Q.push(st), pan[st] = 1, dis[st] = 0, cyf[st] = inf;
    while (!Q.empty()) {
        Re x = Q.front();
        Q.pop();
        pan[x] = 0;
        for (Re i = head[x], to; i; i = a[i].next)
            if (a[i].flow && dis[to = a[i].to] > dis[x] + a[i].w) {
                dis[to] = dis[x] + a[i].w, pre[to] = i;
                cyf[to] = min(cyf[x], a[i].flow);
                if (!pan[to])
                    pan[to] = 1, Q.push(to);
            }
    }
    return dis[ed] != inf;
}
inline void EK(Re st, Re ed) {
    while (SPFA(st, ed)) {
        Re x = ed;
        maxflow += cyf[ed], mincost += (ll)cyf[ed] * dis[ed];
        while (x != st) {  //和最大流一样的更新
            Re i = pre[x];
            a[i].flow -= cyf[ed];
            a[i ^ 1].flow += cyf[ed];
            x = a[i ^ 1].to;
        }
    }
}

signed main() {
    ll kt, mt, kco, mco, co;
    read(n);   // n天
    read(co);  //  买的花费
    read(kt);  //快洗的天数
    read(kco);
    read(mt);
    read(mco);
    for (int i = 1; i <= n; i++) {
        ll xi;
        read(xi);
        add_(0, i, xi, 0);
        add_(i + n, 2 * n + 1, xi, 0);
        add_(0, i + n, inf, co);
        if (i <= n - 1) {
            add_(i, i + 1, inf, 0);
        }
        if (i + kt <= n) {
            add_(i, i + n + kt, inf, kco);
        }
        if (i + mt <= n) {
            add_(i, i + n + mt, inf, mco);
        }
    }
    st = 0;
    ed = 2 * n + 1;
    EK(st, ed);
    printf("%lld\n", mincost);
    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
  • 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

跟FOOD跟相似的题
FOOD
主要就是拆点思想跑个最大流就没了

https://paste.ubuntu.com/p/rdc5DSMhSn/   Ding
https://paste.ubuntu.com/p/y93CkBsPrc/   FOOD

  • 1
  • 2

插座匹配&&网络流
有点麻烦的是对于字符串的处理 题其实很裸

https://paste.ubuntu.com/p/cjf98BZX7Y/   

  • 1

费用流&&模拟
一个字符串的矩阵图，问每个人回到一个房子的最小花费
裸题，直接枚举算距离建边 完事

https://paste.ubuntu.com/p/9f3NfJTV6z/

  • 1

货源地与商家与货物花费运输&&费用流
题目有点点绕感觉，多读读吧。N个商店 M个货源点，有K种货物，然后输入每个商店对第i种货物的需求量 然后就是输入货源地对第i种货物的储存量，然后是K个N*M的矩阵，第j列表示 对于当前第k个矩阵，第j个货源点向第i个商家提供当前种类货物的花费
既然如此，我们就对每种货物运输价值枚举 费用流计算就好了 注意如果当前最大流小于需求量 那么全局无解


#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include<queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
//#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
const int N=1e5,M=1e5+3,inf=2e9;
int x,y,z,w,o=1,n,m,h,t,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];
ll mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];
queue<int>Q;
inline void read(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
    for(Re i=0;i<=n+m+1;++i)dis[i]=inf,pan[i]=0;  //有多少个点就初始化到那个地方去
    Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
    while(!Q.empty()){
    	Re x=Q.front();Q.pop();pan[x]=0;
    	for(Re i=head[x],to;i;i=a[i].next)
            if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w,pre[to]=i;
                cyf[to]=min(cyf[x],a[i].flow);
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
    while(SPFA(st,ed)){
    	Re x=ed;maxflow+=cyf[ed],mincost+=(ll)cyf[ed]*dis[ed];
    	while(x!=st){//和最大流一样的更新
            Re i=pre[x];
            a[i].flow-=cyf[ed];
            a[i^1].flow+=cyf[ed];
            x=a[i^1].to;
    	}
    }
}
ll mia=0,flag=0,k;
ll need[300][300];
ll bos[300][300];
ll cost[300][300];
void cle(ll ki){
    //哪一种商品
ll sum=0;
maxflow=0;
o=1;
mincost=0;
memset(head,0,sizeof(head));
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++){
add_(0,i,bos[i][ki],0);  //源点与  商店
}


for(int i=1;i<=n;i++){
   add_(i+m,m+1+n,need[i][ki],0);
   sum=sum+need[i][ki];
}
for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        add_(i,j+m,inf,cost[j][i]);
    }
}
st=0;
ed=n+m+1;
EK(st,ed);
if(maxflow!=sum){flag=1;}
else{
 mia=mia+mincost;
}

}
signed main(){

 while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF){
    if(n==0&&m==0&&k==0){
        break;
    }
    flag=0;
    mia=0;
    memset(need,0,sizeof(need));

      memset(bos,0,sizeof(bos));
  for(int i=1;i<=n;i++){
    for(int j=1;j<=k;j++){
        read(need[i][j]); // 需求量
    }
  }
  for(int i=1;i<=m;i++){
    for(int j=1;j<=k;j++){
    read(bos[i][j]); //第i个 货源点   存的第j号货的数量
    }
  }

for(int ti=1;ti<=k;ti++){
st=0;
ed=m+n+1;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
   read(cost[i][j]);  // 第  j个 货源点向第i 个商店提供 第 ti种货的 花费

    }
}
cle(ti);
 memset(cost,0,sizeof(cost));
}
if(flag==1){
    printf("-1\n");
    continue;
}
else{
    printf("%lld\n",mia);
}

 }
 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
  • 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
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145

费用流&&裸
输入输出题 - - https://paste.ubuntu.com/p/sQSYVN8MXH/

最大流裸题
有手就行，判断一下最东边最西边的点编号是多少 https://paste.ubuntu.com/p/GPVk23mrkB/

最小割 QAQ
此题是无向图，所以要建立双向，拆点搞搞 你要知道为什么是最小割，拆除城市花费Ai 使得全图不联通 的花费最少

https://paste.ubuntu.com/p/DzGnwDnDM6/

  • 1

最大独立集
有手就行题
有矛盾的建立在一起 跑最大流 用总数减去最大流除2 （因为建重了）

https://paste.ubuntu.com/p/FFk6tbNmBY/

  • 1

一想到追的女生做了别人的女朋友刷题动力直接拉满
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/948277
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号