| 类型 | 最小值 | 最大值 |
|---|---|---|
| unsigned int | 0 | 4294967295 (2^32 - 1) |
| int | -2147483648 | 2147483647 (2^31 - 1) |
| unsigned long | 0 | 4294967295 (2^32 - 1) |
| long | -2147483648 | 2147483647 (2^31 - 1) |
| Unsigned long long | 0 | 18446744073709551615 (2^64 - 1) |
| long long | -9223372036854775808 | 9223372036854775807 (2^63 - 1) |
| unsigned __int64 | 0 | 18446744073709551615 (2^64 - 1) |
| __int64 | -9223372036854775808 | 9223372036854775807 (2^63 - 1) |
给出 1,2,\ldots,n1,2,…,n 的两个排列 P_1P1 和 P_2P2 ，求它们的最长公共子序列。
第一行是一个数 nn。
接下来两行，每行为 nn 个数，为自然数 1,2,\ldots,n1,2,…,n 的一个排列。
一个数，即最长公共子序列的长度。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int INF = 1 << 5;
int p1[maxn];
int a[maxn];
int b[maxn];
inline int read()
{
char c = getchar(); int x = 0;
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
return x;
}
int main()
{
memset(b, INF, sizeof(b));
int n = 0, ind = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
p1[read()] = i;
}
for (int i = 1; i <= n; i++)
{
int x = p1[read()];
*lower_bound(b+1,b+n+1,x)=x;
}
printf("%d", lower_bound(b + 1, b + n + 1, b[0]) - b - 1);
return 0;
}
// P3390.cpp: 定义控制台应用程序的入口点。
//
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char c = getchar(); ll x = 0;
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
return x;
}
ll n, k;
const ll mod = 1e9 + 7;
struct Matrix
{
ll _[105][105];
Matrix()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
this->_[i][j] = 0;
}
Matrix operator* (const Matrix& A)const
{
Matrix z;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int l = 1; l <= n; l++)
z._[i][j] = (z._[i][j] % mod + ((this->_[i][l]) % mod * (A._[l][j]) % mod) % mod) % mod;
return z;
}
};
Matrix T;
inline void print(Matrix& A)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
printf("%lld ", A._[i][j] % mod);
printf("\n");
}
}
inline void getM(Matrix& A)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
A._[i][j] = read();
}
}
inline void Einit(Matrix& E)
{
for (int i = 1; i <= n; i++)
{
E._[i][i] = 1;
}
}
inline void pww(Matrix& S, ll k)
{
while (k )
{
if (k & 1)
S = S * T;
T = T * T;
k >>= 1;
}
}
int main()
{
cin >> n >> k;
getM(T);
Matrix E;
Einit(E);
pww(E, k);
print(E);
return 0;
}
给定一个线性方程组，对其求解
第一行，一个正整数 nn
第二至 n+1n+1行，每行 n+1n+1 个整数，为a_1, a_2 \cdots a_na1,a2?a**n 和 bb，代表一组方程。
共n行，每行一个数，第 ii行为 x_ix**i （保留2位小数）
如果不存在唯一解，在第一行输出"No Solution".
// P3389.cpp: 定义控制台应用程序的入口点。
//
#include <bits/stdc++.h>
#define dd double
#define b n+1
using namespace std;
dd a[300][300];
int n;
const dd eps = 1e-8;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
{
for (int j = 1; j <= n + 1; j++)
cin >> a[i][j];
}
for (int j = 1; j < i; j++)
{
if (fabs(a[j][b]) < fabs(a[i][b]))swap(a[j], a[i]);
}
}
for (int i = 1; i <= n; i++)
{
if (fabs(a[i][i]) <= eps)
{
printf("No Solution\n");
return 0;
}
//debug();
for (int j = i+1; j <= b; j++)
a[i][j] /= a[i][i];
for (int j = 1; j <= n; j++)
if (j != i)
for (int k = i+1; k <= b; k++)
a[j][k] -= a[i][k] * a[j][i];
}
//debug();
for (int i = 1; i <= n; i++)printf("%.2lf\n", a[i][b]);
return 0;
}
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。
接下来 MM 行每行包含三个整数 X_i,Y_i,Z_iX**i,Y**i,Z**i，表示有一条长度为 Z_iZ**i 的无向边连接结点 X_i,Y_iX**i,Y**i。
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
const int INF=0x3f3f3f3f;
int n,m,FA[N];
struct edge
{
int u,v,w;
edge(int a,int b,int c)
{
u=a,v=b,w=c;
}
edge(){}
};
edge e[200000];
inline int read()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
x=x*10+c-‘0‘;
return x;
}
bool cmp(edge i,edge j)
{
return i.w<j.w;
}
int find(int x)
{
if(FA[x]==x)return x;
return FA[x]=find(FA[x]);
}
inline void join(int x,int y)
{
int u=find(x);
int v=find(y);
FA[u]=v;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int u=read();
int v=read();
int w=read();
e[i]=edge(u,v,w);
}
sort(e+1,e+m+1,cmp);
int ttl=0,k=0;
for(int i=1;i<=n;i++)FA[i]=i;
for(int i=1;i<=m;i++)
{
if(find(e[i].u)!=find(e[i].v))
{
join(e[i].u,e[i].v);
k++;
ttl+=e[i].w;
}
if(k==n-1)break;
}
if(k==n-1)cout<<ttl;
else cout<<"orz";
return 0;
}
第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1N?1 行每行包含两个正整数 x, yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 MM 行每行包含两个正整数 a, ba,b，表示询问 aa 结点和 bb 结点的最近公共祖先。
输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
char c=getchar();int x=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
x=x*10+c-‘0‘;
return x;
}
//const int N=10005;
const int N=500005;
vector<int> G[N];
int n,m,FA[N][30],lg[N],DEP[N],s;
void dfs(int u,int fa)
{
FA[u][0]=fa;
DEP[u]=DEP[fa]+1;
for(int i=1;i<lg[DEP[u]];i++)
FA[u][i]=FA[FA[u][i-1]][i-1];
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(fa!=v)
{
dfs(v,u);
}
}
}
int LCA(int x,int y)
{
if(DEP[x]<DEP[y])swap(x,y);
while(DEP[x]!=DEP[y])
x=FA[x][ lg[DEP[x]-DEP[y]] -1 ] ;
if(x==y)return x;
for(int k=lg[DEP[x]]-1;k>=0;k--)
if(FA[x][k]!=FA[y][k])
{
x=FA[x][k];
y=FA[y][k];
}
return FA[x][0];
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
lg[i]=lg[i-1]+(i==(1<<lg[i-1]));
for(int i=1;i<=n-1;i++)
{
int u=read();
int v=read();
G[u].push_back(v);
G[v].push_back(u);
}
dfs(s,0);
for(int i=1;i<=m;i++)
{
int u=read();
int v=read();
printf("%d\n",LCA(u,v));
}
return 0;
}
给出一个 nn 个点，mm 条边的无向图，求图的割点。
第一行输入两个正整数 n,mn,m。
下面 mm 行每行输入两个正整数 x,yx,y 表示 xx 到 yy 有一条边。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
char c = getchar(); int x = 0;
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
return x;
}
const int N=20005;
int n,m,DFN[N],LOW[N],ts,cnt,cut[N];
bool in[N];
vector<int> G[N];
void Tarjan(int u,int fa)
{
int s=0;
DFN[u]=LOW[u]=++ts;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(DFN[v]==0)
{
Tarjan(v,u);
LOW[u]=min(LOW[v],LOW[u]);
if(fa==0)s++;
else if(LOW[v]>=DFN[u])cut[u]=1;
}
LOW[u]=min(LOW[u],DFN[v]);
}
if(s>=2&&fa==0)cut[u]=1;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u=read();
int v=read();
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)if(DFN[i]==0)Tarjan (i,0);
int ans=0;
for(int i=1;i<=n;i++)if(cut[i])ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++)if(cut[i])cout<<i<<‘ ‘;
return 0;
}
给定一个 nn 个点 mm 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
第一行两个正整数 n,mn,m
第二行 nn 个整数，依次代表点权
第三至 m+2m+2 行，每行两个整数 u,vu,v，表示一条 u\rightarrow vu→v 的有向边。
#include <bits/stdc++.h>
using namespace std;
const int N=10005,INF=0x3f3f3f3f;
int PW[N],DFN[N],LOW[N],n,m,ts,COL[N],cc,WT[N];
vector<int>G[N];
int g[N][N];
stack<int> S;
bool in[N];
inline int read()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(; isdigit(c);c=getchar())
x=x*10+c-‘0‘;
return x;
}
void Tarjan(int u)
{
// cout<<"Dsd"<<endl;
LOW[u]=DFN[u]=++ts;
S.push(u);
in[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!DFN[v])
{
Tarjan(v);
LOW[u]=min(LOW[u],LOW[v]);
}
else if(in[v])
{
LOW[u]=min(LOW[v],LOW[u]);
}
}
if(DFN[u]==LOW[u])
{
cc++;
while(1)
{
int x=S.top();
S.pop();
in[x]=0;
COL[x]=cc;
WT[cc]+=PW[x];
//
// cout<<"IDD"<<x<<endl;
if(x==u)break;
}
}
}
int f[N];
int dp(int u)
{
// cout<<"DP:f"<<u<<" "<<endl;
if(f[u])return f[u];
f[u]=WT[u];
for(int i=1;i<=cc;i++)
{
if(g[u][i])
{
f[u]=max(f[u],dp(i)+WT[u]);
// cout<<"INS"<<endl;
}
}
return f[u];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)PW[i]=read();
for(int i=1;i<=m;i++)
{
int u=read();
int v=read();
G[u].push_back(v);
}
for(int i=1;i<=n;i++)if(!DFN[i])Tarjan(i);
// cout<<COL[1]<<" "<<COL[2]<<endl;
for(int i=1;i<=n;i++)
{
for(int j=0;j<G[i].size();j++)
{
int u=i,v=G[i][j];
if(COL[u]!=COL[v])
{
g[COL[u]][COL[v]]=1;
}
}
}
int maxx=0;
for(int i=1;i<=cc;i++)maxx=max(maxx,dp(i));
cout<<maxx;
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn = 1005;
int edge[maxn][maxn];
int cx[maxn];
int cy[maxn];
int vis[maxn];
inline int read()
{
int x = 0; char c = getchar();
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
return x;
}
int n, m, e;
int path(int u)
{
int v;
for (v = 1; v <= m; v++)
if (edge[u][v] && !vis[v])
{
vis[v] = 1;
if (cy[v] == -1 || path(cy[v]))
{
cx[u] = v;
cy[v] = u;
return 1;
}
}
return 0;
}
int maxmatch()
{
int res = 0;
int u = 0;
for (u = 1; u <= n; u++)
{
if (cx[u] == -1)
{
memset(vis, 0, sizeof(vis));
res += path(u);
}
}
return res;
}
int main()
{
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
cin >> n >> m >> e;
for (int i = 1; i <= e; i++)
{
int u = 0, v = 0;
cin >> u >> v;
//u = read();
//v = read();
if (v > m)continue;
edge[u][v] = 1;
}
cout << maxmatch();
return 0;
}
// P1939.cpp: 定义控制台应用程序的入口点。
//
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char c = getchar(); ll x = 0;
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
return x;
}
const ll mod = 1e9 + 7, n = 3;
ll q;
struct Mat
{
ll _[5][5];
Mat()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
this->_[i][j] = 0;
}
Mat operator* (const Mat& A)const
{
Mat R;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
R._[i][j] = (R._[i][j] +( this->_[i][k] * A._[k][j])%mod)%mod;
return R;
}
};
Mat X,E;
Mat pww(ll k,Mat X)
{
Mat A = E;
while (k)
{
if (k & 1)
A = A * X;
X = X * X;
k >>= 1;
}
return A;
}
int main()
{
int T = read();
for (int i = 1; i <= n; i++)E._[i][i] = 1;
X._[1][1] = X._[1][3] = X._[2][1] = X._[3][2] = 1;
while (T--)
{
q = read();
Mat F=pww(q-1,X);
ll ans = 0;
for (int i = 1; i <= n; i++)
ans = (ans+F._[3][i])%mod;
printf("%lld\n", ans);
}
return 0;
}
Dijkstra
#include<bits/stdc++.h>
using namespace std;
const int N=100005,INF=0x3f3f3f3f;
int n,m,s,d[N];
inline int read()
{
char c=getchar();int x=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
x=x*10+c-‘0‘;
return x;
}
struct node
{
int w,v;
node(int a,int b)
{
w=a;
v=b;
}
};
vector<node>G[N];
priority_queue< pair<int,int> > Q;
bool vis[N];
void Dijk()
{
memset(d,0x3f,sizeof(d));
d[s]=0;
Q.push( make_pair(0,s));
while(!Q.empty())
{
int u=Q.top().second;
Q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i].v,w=G[u][i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
Q.push(make_pair(-d[v],v));
}
}
}
}
int main()
{
n=read();
m=read();
s=read();
for(int i=1;i<=m;i++)
{
int u=read();
int v=read();
int w=read();
G[u].push_back(node(w,v));
}
Dijk();
for(int i=1;i<=n;i++)
printf("%d ",d[i]);
return 0;
}
负环
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <list>
#include <memory.h>
using namespace std;
int n, m;
const int maxn = 20005;
struct edge
{
int to, w;
edge()
{
to = 0;
w = 0;
}
edge(int a, int b)
{
to = a;
w = b;
}
};
vector< vector<edge> > G;
int d[maxn];
const int INF = 1 << 30;
int cnt[maxn];
bool flag = 1;
bool v[maxn];
inline int read()
{
bool minus = 0;
int x = 0; char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == ‘-‘)minus = 1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
if (minus)return -x;
return x;
}
inline void intial()
{
G.clear();
memset(v, 0, sizeof(v));
for (int i = 0; i < maxn; i++)
d[i] = INF;
memset(cnt, 0, sizeof(cnt));
}
struct node
{
int x;
node(int a)
{
x = a;
}
bool operator <(const node& i)const
{
return this->x > i.x;
}
};
void SPFA(int start)
{
priority_queue<node> Q;
//list<int>Q;
Q.push(node(start));
v[start] = 1;
d[start] = 0;
cnt[start] = 1;
while (!Q.empty())
{
int x = Q.top().x;
Q.pop();
v[x] = 0;
for (int i = 0; i < G[x].size(); i++)
{
int t = G[x][i].to, w = G[x][i].w;
if (d[x] + w < d[t])
{
d[t] = d[x] + w;
cnt[t] = cnt[x] + 1;
if (!v[t])
{
if (cnt[t] > n)
{
flag = 0;
return;
}
v[t] = 1;
Q.push(node(t));
}
}
}
}
}
int main()
{
// freopen("C:\\Users\\Administrator\\Downloads\\testdata (16).in", "r", stdin);
int oo;
oo = read();
for (int pp = 1; pp <= oo; pp++)
{
flag = 1;
intial();
n = read();
m = read();
vector<edge>samp;
G.assign(n + 10, samp);
for (int i = 1; i <= m; i++)
{
int a, b, w;
a = read();
b = read();
w = read();
if (w < 0)
{
G[a].push_back(edge(b, w));
}
else
{
G[a].push_back(edge(b, w));
G[b].push_back(edge(a, w));
}
}
SPFA(1);
if (flag == 0)
cout << "YE5" << endl;
if (flag)
cout << "N0" << endl;
}
return 0;
}
如题，已知一个数列，你需要进行下面两种操作：
第一行包含两个整数 NN、MM，分别表示该数列数字的个数和操作的总个数。
第二行包含 NN 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 MM 行每行包含 22 或 44个整数，表示一个操作，具体如下：
操作 11： 格式：1 x y k 含义：将区间 [x,y][x,y] 内每个数加上 k；
操作 22： 格式：2 x 含义：输出第 x 个数的值。
输出包含若干行整数，即为所有操作 22 的结果。
// Segtree.cpp: 定义控制台应用程序的入口点。
//
#include <bits/stdc++.h>
#define ll long long
#define mid ((L+R)>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define len (R-L+1)
using namespace std;
inline ll read()
{
char c = getchar(); ll x = 0;
bool minus = 0;
for (; !isdigit(c); c = getchar())
if (c == ‘-‘)minus = 1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
if (minus)return -x;
return x;
}
const ll N = 1000001;
ll n, m, l, r, dlt, nowsum;
ll a[N], sum[N << 1], tag[N << 1];
inline void push_up(ll o)
{
sum[o] = sum[ls] + sum[rs];
}
void construct(ll o, ll L, ll R)
{
tag[o] = 0;
if (L == R)
{
sum[o] = a[L];
return;
}
construct(ls, L, mid);
construct(rs, mid + 1, R);
push_up(o);
}
inline void ff(ll o, ll L, ll R, ll d)
{
tag[o] += d;
sum[o] += d * len;
}
inline void push_down(ll o, ll L, ll R)
{
ff(ls, L, mid, tag[o]);
ff(rs, mid + 1, R, tag[o]);
tag[o] = 0;
}
void update(ll o, ll L, ll R)
{
if (l <= L && R <= r)
{
tag[o] += dlt;
sum[o] += dlt * len;
return;
}
push_down(o, L, R);
if (l <= mid)update(ls, L, mid);
if (r > mid)update(rs, mid + 1, R);
push_up(o);
}
ll query(ll o, ll L, ll R)
{
if (l <= L && R <= r)
{
return sum[o];
}
ll res = 0;
push_down(o, L, R);
if (l <= mid)res += query(ls, L, mid);
if (r > mid)if (r > mid)res += query(rs, mid + 1, R);
push_up(o);
return res;
}
int main()
{
cin >> n >> m;
for (ll i = 1; i <= n; i++)
a[i] = read();
construct(1, 1, n);
while (m--)
{
ll q = read();
if (q == 1)
{
l = read();
r = read();
dlt = read();
update(1, 1, n);
}
if (q == 2)
{
l = read();
r = l;
printf("%lld\n", query(1, 1, n));
}
}
return 0;
}
Dicnic 网络最大流
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <memory.h>
using namespace std;
const int maxn = 10005;
const int maxm = 1000005 * 2;//边数max
const int INF = 1 << 30;
int ind = 0;
int r[maxm];//残余流量
int vec[maxm];//编号x的边指向的点
int dep[maxn];//点的层次编号数组
list<int>G[maxn];//记录每个点的出边
inline int read()
{
char c = getchar(); int x = 0;
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + c - ‘0‘;
return x;
}
int bfs(int s, int t)
{
queue<int>Q;
while (!Q.empty())Q.pop();
memset(dep, 0, sizeof(dep));
dep[s] = 1;
Q.push(s);
while (!Q.empty())
{
// cout << "*****bfs1****" << endl;
int x = Q.front();
Q.pop();
for (list<int>::iterator it = G[x].begin(); it != G[x].end(); it++)
{
int i = *it;
if ((r[i] > 0) && (dep[vec[i]] == 0))
{
// cout << "*****bfs2****x=" << x << endl;
dep[vec[i]] = dep[x] + 1;
Q.push(vec[i]);
}
}
}
if (dep[t] > 0)return 1;
if (dep[t] == 0)return 0;
}
int dfs(int s, int mxfl, int t)
{
if (s == t)return mxfl;
for (list<int>::iterator it = G[s].begin(); it != G[s].end(); it++)
{
int i = *it;
//cout << "&****dfs 1************" << endl;
if ((dep[vec[i]] == dep[s] + 1) && (r[i] > 0))
{
//cout << "&****dfs2************" << endl;
int di = dfs(vec[i], min(r[i], mxfl), t);
//cout << "&***dfs3************" << endl;
//cout << "di=" << di << endl;
if (di > 0)
{
r[i] -= di;
r[i ^ 1] += di;
return di;
}
}
}
return 0;
}
inline void add(int u, int v, int w)
{
r[ind] += w;
G[u].push_back(ind);
vec[ind] = v;
ind++;
}
int Dinic(int s, int t)
{
int maxflow = 0;
while (bfs(s, t))
{
// cout << "&****dinic 1************" << endl;
while (1)
{
// cout << "&****dinic 1************" << endl;
int d = dfs(s, INF, t);
if (d == 0)break;
maxflow += d;
}
}
return maxflow;
}
int main()
{
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++)
{
int u, v, w;
u = read();
v = read();
w = read();
add(u, v, w);
add(v, u, 0);
}
cout << Dinic(s, t);
return 0;
}
线段树
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#define ll long long
using namespace std;
const int maxn = 100005;
const int maxm = 1000005;
ll a[maxn];
ll sum[maxm];
ll addv[maxm];
ll mulv[maxm];
int p;
inline ll read()
{
char c = getchar(); ll x = 0;
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar())
x = x * 10 + (c - ‘0‘);
return x;
}
void cons(int o, int L, int R)
{
addv[o] = 0;
mulv[o] = 1;
if (L == R)
sum[o] = a[L];
else
{
int mid = (L + R) / 2;
cons(o * 2, L, mid);
cons(o * 2 + 1, mid + 1, R);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
}
sum[o] %= p;
return;
}
inline void maintain(int o, int L, int R)
{
int mid = (L + R) / 2;
sum[o * 2] = (sum[o * 2] * mulv[o] + addv[o] * (mid - L + 1)) % p;
sum[o * 2 + 1] = (sum[o * 2 + 1] * mulv[o] + addv[o] * (R - mid)) % p;
mulv[o * 2] = (mulv[o] * mulv[o * 2]) % p;
mulv[o * 2 + 1] = (mulv[o] * mulv[o * 2 + 1]) % p;
addv[o * 2] = (addv[o * 2] * mulv[o] + addv[o]) % p;
addv[o * 2 + 1] = (addv[o * 2 + 1] * mulv[o] + addv[o]) % p;
addv[o] = 0;
mulv[o] = 1;
}
ll ql, qr;
void u_add(int o, int L, int R, int d)
{
if (R<ql || L>qr)return;
if (ql <= L && R <= qr)
{
addv[o] = (addv[o] + d) % p;
sum[o] = (sum[o] + d * (R - L + 1)) % p;
return;
}
maintain(o, L, R);
int mid = (L + R) / 2;
u_add(2 * o, L, mid, d);
u_add(2 * o + 1, mid + 1, R, d);
sum[o] = (sum[o * 2] + sum[o * 2 + 1]) % p;
return;
}
void u_mul(int o, int L, int R, int m)
{
if (R<ql || L>qr)return;
if (ql <= L && R <= qr)
{
sum[o] = (sum[o] * m) % p;
addv[o] = (addv[o] * m) % p;
mulv[o] = (mulv[o] * m) % p;
return;
}
maintain(o, L, R);
int mid = (L + R) / 2;
u_mul(2 * o, L, mid, m);
u_mul(2 * o + 1, mid + 1, R, m);
sum[o] = (sum[o * 2] + sum[o * 2 + 1]) % p;
return;
}
ll query(int o, int L, int R)//intial d=0,m=1;
{
if (R<ql || L>qr)return 0;
if (ql <= L && R <= qr)
return sum[o];
ll s1 = 0, s2 = 0;
maintain(o, L, R);
int mid = (L + R) / 2;
s1 = query(2 * o, L, mid);
s2 = query(2 * o + 1, mid + 1, R);
return (s1 + s2) % p;
}
int main()
{
memset(mulv, 1, sizeof(mulv));
int n, m;
cin >> n >> m >> p;
for (int i = 1; i <= n; i++)
a[i] = read();
cons(1, 1, n);
for (int i = 1; i <= m; i++)
{
ll g = 0;
g = read();
ql = read();
qr = read();
if (g == 1)
{
int k = read();
u_mul(1, 1, n, k);
continue;
}
if (g == 2)
{
int k = read();
u_add(1, 1, n, k);
continue;
}
if (g == 3)
{
ll s = query(1, 1, n);
printf("%d\n", s);
continue;
}
}
return 0;
}
原文：https://www.cnblogs.com/kion/p/14129548.html