赞
踩
太扎心了《所以还是继续学习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]); } } 好了开始今日的学习吧,啥也不会的大彩笔
拉格朗日插值&&懵逼到懵懂
先来一个例题 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; }
网络流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; }
网络流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; }
网络流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; }
网络流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; }
网络流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; }
跟FOOD跟相似的题
FOOD
主要就是拆点思想跑个最大流就没了
https://paste.ubuntu.com/p/rdc5DSMhSn/ Ding
https://paste.ubuntu.com/p/y93CkBsPrc/ FOOD
插座匹配&&网络流
有点麻烦的是对于字符串的处理 题其实很裸
https://paste.ubuntu.com/p/cjf98BZX7Y/
费用流&&模拟
一个字符串的矩阵图,问每个人回到一个房子的最小花费
裸题,直接枚举算距离建边 完事
https://paste.ubuntu.com/p/9f3NfJTV6z/
货源地与商家与货物花费运输&&费用流
题目有点点绕感觉,多读读吧。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; }
费用流&&裸
输入输出题 - - https://paste.ubuntu.com/p/sQSYVN8MXH/
最大流裸题
有手就行,判断一下最东边最西边的点编号是多少 https://paste.ubuntu.com/p/GPVk23mrkB/
最小割 QAQ
此题是无向图,所以要建立双向,拆点搞搞 你要知道为什么是最小割,拆除城市花费Ai 使得全图不联通 的花费最少
https://paste.ubuntu.com/p/DzGnwDnDM6/
最大独立集
有手就行题
有矛盾的建立在一起 跑最大流 用总数减去最大流除2 (因为建重了)
https://paste.ubuntu.com/p/FFk6tbNmBY/
一想到追的女生做了别人的女朋友刷题动力直接拉满
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。