目录
对于数组来说如果我们要在区间[L,R]上增加k,那么可以在L位置上增加K,R+1位置上减小K。
那么对于一颗数来说,如果我们要记录(x,y)之间的信息,那么可以在x和y位置+k,lca(x,y)位置减去2*k,访问的时候从叶子节点回溯到跟即是所求的值。题目:https://www.acwing.com/problem/content/description/354/
割边判定法则:无向变( x,y)是桥,当且仅当搜索树上存在x的一个子节点y,满足:
dfn[x]<low[y]
#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 10;
int head[N], nextt[N * 2], to[N * 2], cnt = 2;
int n, m,tot=1;
int dfn[N], low[N];
bool bridge[N * 2];
void add(int u, int v) {
to[cnt] = v, nextt[cnt] = head[u], head[u] = cnt++;
}
void tarjan(int rt, int edge) {
dfn[rt] = low[rt] = tot++;
for (int i = head[rt]; i; i = nextt[i]) {
int v = to[i];
if (!dfn[v]) {
tarjan(v,i);
low[rt] = min(low[rt],low[v]);
if (dfn[rt] < low[v])bridge[i] = true;
}
else if (edge != (i ^ 1))low[rt] = min(low[rt],dfn[v]);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
add(u, v); add(v, u);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])tarjan(i, 0);
}
for (int i = 2; i < cnt; i++) {
if (bridge[i])cout << to[i] << " "<<to[i ^ 1] << endl;
}
return 0;
}
判定法则:若x不是搜索树的根节点,则x是割点当且仅当搜索树上存在x的一个子节点y,满足:
dfn[x]<=low[y]
特别地,若x是搜索树的根节点,则x是割点当且仅当搜索树上至少存在两个子节点y1,y2,满足上述条件。
#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1000*100+10;
int n,m,cnt,num,root;
int head[N],ne[N*2],to[N*2];
int dfn[N],low[N];
bool cut[N];
void add(int u,int v){
to[cnt]=v,ne[cnt]=head[u],head[u]=cnt++;
to[cnt]=u,ne[cnt]=head[v],head[v]=cnt++;
}
void tarjan_point(int x){
dfn[x]=low[x]=++num;
int flag=0;
for(int i=head[x];i!=-1;i=ne[i]){
int y=to[i];
if(!dfn[y]){
tarjan_point(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1)cut[x]=true;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
scanf("%d %d",&n,&m);
cnt=2;
for(int i=1;i<=n;i++)head[i]=-1;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u==v)continue;
add(u,v);
}
for(int i=1;i<=n;i++)dfn[i]=low[i]=0,cut[i]=false;
for(int i=1;i<=n;i++){
if(!dfn[i])root=i,tarjan_point(i);
}
cout<<"This is all:"<<endl;
for(int i=1;i<=n;i++)
if(cut[i])
printf("%d\n",i);
}
把一个全排列从小到大排序,对于给定的任意一个排列我们可以求出他属于第几个排列,即是求出有多少个排列比他小。
有关至少参看:康托展开
以下给出用树状数组优化后的算法:
#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9 + 7;
const int MAXN=1e7;
int n,m,cnt;
int f[20],dat[20],vis[20];
struct {
int s[20];
void init(){
for(int i=1;i<=n;i++)s[i]=0;
}
int lowerbit(int x){return x&-x;}
void add(int x,int k){while(x<=n)s[x]+=k,x+=lowerbit(x);}
int query(int x){int ans=0;while(x)ans+=s[x],x-=lowerbit(x);return ans;}
}bit;
void init(){
f[0]=1;
for(int i=1;i<=n;i++)f[i]=f[i-1]*i;
while(m){
dat[++cnt]=m%10;
m/=10;
}
}
int kangtuo(){
int ans=0;
for(int i=cnt;i;i--){
ans+=bit.query(dat[i]-1)*f[i-1];
bit.add(dat[i],-1);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
bit.init();
for(int i=1;i<=n;i++)bit.add(i,1);
init();
int n=kangtuo();
printf("%d\n",n+1);
return 0;
}
康托展开的逆运算:
就是求解第n个排列具体是什么
#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9 + 7;
const int MAXN=1e7;
int n,m,cnt;
int f[20],dat[20],vis[20];
void init(){
f[0]=1;
for(int i=1;i<=n;i++)f[i]=f[i-1]*i;
}
int kangtuo_inver(int x){
int num;
int a[20];
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=n;i++){
num=x/f[n-i];
x=x%f[n-i];
int cnt=0;
for(int j=1;j<=n;j++){
if(cnt==num&&a[j]<n+1){
dat[i]=a[j];
a[j]=n+1;
break;
}
if(a[j]<n+1)cnt++;
}
}
}
int main(){
scanf("%d%d",&n,&m);
init();
kangtuo_inver(m);
for(int i=1;i<=n;i++)printf("%d",dat[i]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N =1e6 + 10;
int M;
char s[N];
int n,m;
int rak[N],h[N],tax[N],tp[N],sa[N];
void qsort(){
for(int i=0;i<M;i++)tax[i]=0;
for(int i=1;i<=n;i++)tax[rak[i]]++;
for(int i=1;i<=M;i++)tax[i]+=tax[i-1];
for(int i=N;i>=1;i--)sa[tax[rak[tp[i]]]--]=tp[i];
}
void get_sa(){
M=130;
for(int i=1;i<=n;i++)rak[i]=s[i]-'0'+1,tp[i]=i;
qsort();
for(int w=1,p=0;p<=n;w<<=1,M=p){
p=0;
for(int i=1;i<=w;i++)tp[++p]=n-w+i;
for(int i=1;i<=n;i++)if(sa[i]>w)tp[++p]=sa[i]-w;
qsort();
swap(tp,rak);
rak[sa[1]]=p=1;
for(int i=2;i<=n;i++){
rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
}
if(p>=n)break;
}
}
void get_h(){
int j,k=0;
for(int i=1;i<=n;i++){
if(k)k--;
int j=sa[rak[i]-1];
while(s[i+k]==s[j+k])k++;
h[rak[i]]=k;
}
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
get_sa();
get_h();
for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
cout<<endl;
return 0;
}
const int N = 1000*100+10;
int sz,last;
struct state{
int len,link;
map<char,int>next;
}st[N*2];
void init(){
st[0].len=0;
st[0].link=-1;
sz++;
last=0;
}
void sa_extend(char c){
int cur=sz++;
st[cur].len=st[last].len+1;
int p=last;
while(p!=-1&&!st[p].next.count(c)){
st[p].next[c]=cur;
p=st[p].link;
}
if(p==-1)st[cur].link=0;
else{
int q=st[p].next[c];
if(st[p].len+1==st[q].len)st[cur].link=q;
else{
int clone=sz++;
st[clone].len=st[p].len+1;
st[clone].next=st[q].next;
st[clone].link=st[q].link;
while(p!=-1&&st[p].next[c]==q){
st[p].next[c]=clone;
p=st[p].link;
}
st[q].link=st[cur].link=clone;
}
}
last=cur;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1000+10;
char s[N][N+10];
int mx1=0,mx2=0;
int a[N][N],h[N];
int L[2][N],R[2][N],up[2][N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=s[i][j]-'0';
}
}
int k=0;
for(int i=1;i<=n;i++){
k^=1;
int lo=0,ro=m+1;
for(int j=1;j<=m;j++){
if(a[i][j]==0)up[k][j]=L[k][j]=0,lo=j;
else {
up[k][j]=i==1?1:up[k^1][j]+1;
L[k][j]=i==1?lo+1:max(L[k^1][j],lo+1);
}
}
for(int j=m;j;j--){
if(a[i][j]==0)R[k][j]=m+1,ro=j;
else{
R[k][j]=i==1?ro-1:min(R[k^1][j],ro-1);
int len=R[k][j]-L[k][j]+1;
int height=up[k][j];
ans=max(ans,heiht*len);
}
}
}
printf("%d\n",ans);
return 0;
}
变量名不能和关键字相同
struct Line_base{
ll b[64];
int cnt; //维数
bool flag; //能否被0表示
void init(){
cnt=0;
flag=false;
memset(b,0,sizeof(b));
}
void Copy(Line_base B){
cnt=B.cnt;
flag=B.flag;
memcpy(b,B.b,sizeof(b));
}
void Insert(ll x){
for(int i=63;i>=0;i--){
if(x&(1LL<<i))
if(b[i])x^=b[i];
else{
b[i]=x;
cnt++;
return;
}
}
flag=true;
}
bool check(ll x){ //检查x是否能被已存在的基表示
for(int i=63;i>=0;i--){
if(x&(1LL<<i))
if(b[i])x^=b[i];
else return false;
}
return true;
}
}B1,B2,B3;
高斯消元求法(基是对角矩阵)
void cal() {
for (int i = 0; i < n; ++i)
for (int j = MAX_BASE; j >= 0; --j)
if (a[i] >> j & 1) {
if (b[j]) a[i] ^= b[j];
else {
b[j] = a[i];
for (int k = j - 1; k >= 0; --k) if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
for (int k = j + 1; k <= MAX_BASE; ++k) if (b[k] >> j & 1) b[k] ^= b[j];
break;
}
}
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 55
using namespace std;
int A[maxn][maxn],V[maxn];
int cn,bestn; //当前节点数,最大节点数
int n;
int check(int x){
for (int i=1;i<x;i++){
if (V[i] && !A[x][i]) return 0;
}
return 1;
}
void dfs(int x){
if (x>n){ //此处记录最大团
bestn=max(cn,bestn);
return ;
}
if (check(x)){
cn++;
V[x]=1;
dfs(x+1);
cn--;
}
if (cn+n-x>bestn){
V[x]=0;
dfs(x+1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
while (cin >> n && n){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++) cin >> A[i][j];
}
cn=bestn=0;
memset(V,0,sizeof(V));
dfs(1);
cout << bestn << endl;
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <map>
typedef long long int ll;
const int MOD = (int)1e9 + 7;
const int INF = 99999999;
using namespace std;
int n, m;
map<string, int> city;
int dp1[1 << 8][35];
int dp2[1 << 8];
int d[35][35];
int vis[35];
bool check(int s)
{
for (int i = 0; i < 4; i++)
{
if (((s & 3) != 3) && ((s & 3) != 0))
return false;
s >>= 2;
}
return true;
}
int main()
{
while (~scanf("%d%d", &n, &m) && (n || m))
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = (i == j) ? 0 : INF;
string s1, s2;
int w;
for (int i = 0; i < n; i++)
{
cin >> s1;
city[s1] = i;
}
for (int i = 0; i < m; i++)
{
cin >> s1 >> s2 >> w;
int u = city[s1];
int v = city[s2];
if (w < d[u][v])
d[u][v] = d[v][u] = w;
}
// Floyd
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 0; i < 8; i++)
{
cin >> s1;
for (int j = 0; j < n; j++)
dp1[1 << i][j] = d[j][city[s1]];
}
for (int i = 0; i < (1 << 8); i++)
{
if (!(i & (i - 1)))
continue;
for (int j = 0; j < n; j++)
{
dp1[i][j] = INF;
for (int sub = (i - 1) & i; sub != 0; sub = (sub - 1) & i)
dp1[i][j] = min(dp1[i][j], dp1[sub][j] + dp1[i - sub][j]);
}
memset(vis, 0, sizeof(vis));
int min_w, min_i;
for (int j = 0; j < n; j++)
{
min_w = INF;
for (int k = 0; k < n; k++)
{
if (dp1[i][k] < min_w && !vis[k])
{
min_w = dp1[i][k];
min_i = k;
}
}
vis[min_i] = 1;
for (int k = 0; k < n; k++)
dp1[i][min_i] = min(dp1[i][min_i], dp1[i][k] + d[k][min_i]);
}
}
for (int i = 0; i < (1 << 8); i++)
{
dp2[i] = INF;
for (int j = 0; j < n; j++)
dp2[i] = min(dp2[i], dp1[i][j]);
}
for (int i = 0; i < (1 << 8); i++)
{
if (check(i))
{
for (int j = i; j != 0; j = (j - 1) & i)
{
if (check(j))
dp2[i] = min(dp2[i], dp2[j] + dp2[i - j]);
}
}
}
printf("%d\n", dp2[(1 << 8) - 1]);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
const int N =1000*10000+10;
struct Complex{
double x,y;
Complex(double xx=0,double yy=0){x=xx,y=yy;}
Complex operator + (Complex a){return Complex(x+a.x,y+a.y);}
Complex operator - (Complex a){return Complex(x-a.x,y-a.y);}
Complex operator * (Complex a){return Complex(x*a.x-y*a.y,x*a.y+a.x*y);}
}a[N],b[N];
int n,m,limit=1,l=0,r[N];
void FFT(Complex *A,int type){
for(int i=0;i<limit;i++)
if(i<r[i])swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1){
Complex wn(cos(PI/mid),type*sin(PI/mid));
for(int R=mid<<1,j=0;j<limit;j+=R){
Complex w(1,0);
for(int k=0;k<mid;k++,w=w*wn){
Complex x=A[j+k],y=w*A[j+mid+k];
A[j+k]=x+y;
A[j+mid+k]=x-y;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)scanf("%lf",&a[i].x);
for(int i=0;i<=m;i++)scanf("%lf",&b[i].x);
while(limit<=n+m)limit<<=1,l++;
for(int i=0;i<limit;i++){
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
FFT(a,1);
FFT(b,1);
for(int i=0;i<=limit;i++)a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=0;i<=n+m;i++){
printf("%d ",(int)(a[i].x/limit+0.5));
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 10 * 1e6 + 10, P = 998244353, G = 3, Gi = 332748118;
char buf[1<<21], *p1 = buf, *p2 = buf;
int N, M, limit = 1, L, r[MAXN];
ll a[MAXN], b[MAXN];
inline ll fastpow(ll a, ll k) {
ll base = 1;
while(k) {
if(k & 1) base = (base * a ) % P;
a = (a * a) % P;
k >>= 1;
}
return base % P;
}
inline void NTT(ll *A, int type) {
for(int i = 0; i < limit; i++)
if(i < r[i]) swap(A[i], A[r[i]]);
for(int mid = 1; mid < limit; mid <<= 1) {
ll Wn = fastpow( type == 1 ? G : Gi , (P - 1) / (mid << 1));
for(int j = 0; j < limit; j += (mid << 1)) {
ll w = 1;
for(int k = 0; k < mid; k++, w = (w * Wn) % P) {
int x = A[j + k], y = w * A[j + k + mid] % P;
A[j + k] = (x + y) % P,
A[j + k + mid] = (x - y + P) % P;
}
}
}
}
int main() {
scanf("%d%d",&N,&M);
for(int i = 0; i <= N; i++) scanf("%lld",a+i),a[i] = (a[i] + P) % P;
for(int i = 0; i <= M; i++) scanf("%lld",b+i),b[i] = (b[i] + P) % P;
while(limit <= N + M) limit <<= 1, L++;
for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
NTT(a, 1);
NTT(b, 1);
for(int i = 0; i < limit; i++) a[i] = (a[i] * b[i]) % P;
NTT(a, -1);
ll inv = fastpow(limit, P - 2);
for(int i = 0; i <= N + M; i++)
printf("%lld ", (a[i] * inv) % P);
return 0;
}
struct Palindromic_Tree {
int next[MAXN][26];
int fail[MAXN];
int cnt[MAXN];
int num[MAXN];
int len[MAXN];
int S[MAXN];
int last;
int n;
int p;
int newnode(int l)
{
for (int i = 0; i < 26; ++i) next[p][i] = 0;
cnt[p] = 0;
num[p] = 0;
len[p] = l;
return p++;
}
void Init()
{
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
S[n] = -1;
fail[0] = 1;
}
int get_fail(int x)
{
while (S[n - len[x] - 1] != S[n])x = fail[x];
return x;
}
void add(int c)
{
S[++n] = c;
int cur = get_fail(last);
if (!next[cur][c])
{
int now = newnode(len[cur] + 2);
fail[now] = next[get_fail(fail[cur])][c];
next[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = next[cur][c];
cnt[last]++;
}
ll count()
{
ll res = p * 1ll;
for (int i = p - 1; i >= 0; --i) cnt[fail[i]] += cnt[i];
return (res - 2);//本质不同的回文串数量
}
}pam;
struct SAM {
/*sam.init(); 空间要开四倍
ll c = 0; 不同子串的数量
for (int i = 0; i < len; ++i) {
sam.extend(s[i] - 'a');
c += i + 1LL - sam.len[sam.fa[sam.last]];
}*/
static const int M = MAXN << 2;
int nxt[M][27], len[M] = { -1 }, fa[M], sz = 2, last = 1;
int newnode() {
memset(nxt[sz], 0, sizeof nxt[sz]);
len[sz] = len[last] + 1;
return last = sz++;
}
void init() {
sz = 2, last = 1;
memset(nxt[1], 0, sizeof nxt[1]);
}
void extend(int ch) {
int p = last, np = newnode();
for (; p && !nxt[p][ch]; p = fa[p]) nxt[p][ch] = np;
if (!p) {
fa[np] = 1;
return;
}
int q = nxt[p][ch];
if (len[p] + 1 == len[q]) fa[np] = q;
else {
int nq = sz++;
len[nq] = len[p] + 1;
memcpy(nxt[nq], nxt[q], sizeof nxt[0]);
fa[nq] = fa[q];
fa[np] = fa[q] = nq;
for (; nxt[p][ch] == q; p = fa[p]) nxt[p][ch] = nq;
}
}
} sam;
#include<bits/stdc++.h>
using namespace std;
const int N = 10000+10,M = 40000+10;
int n,m;
int head[N],nextt[M*2],to[M*2],cnt=1;
int sk[N*100],ans[N*100];
int top,t;
bool vis[N*100];
void add(int u,int v){
to[cnt]=v,nextt[cnt]=head[u],head[u]=cnt++;
}
void euler(){
sk[++top]=1;
while(top>0){
int x=sk[top],i=head[x];
while(i&&(vis[i]))i=nextt[i];
if(i){
sk[++top]=to[i];
vis[i]=vis[i^1]=true;
head[x]=nextt[i];
}
else {
top--;
ans[++t]=x;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
euler();
for(int i=t;i;i--)printf("%d\n",ans[i]);
return 0;
}
/*
cnt: 强联通分量的数目
c[x]:x点属于的强联通分量的的编号
scc[x]:编号为x的强联通分量中的点
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int head[N],nextt[N],to[N];
int hd[N],ne[N],To[N];
int dfn[N],low[N];
int num,top,tot,cnt,tc;
int s[N],ins[N],c[N];
int in[N],out[N];
vector<int>scc[N];
void add(int u,int v){
to[++tot]=v,nextt[tot]=head[u],head[u]=tot;
}
void add_c(int u,int v){
To[++tc]=v,ne[tc]=hd[u],hd[u]=tc;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
s[++top]=x,ins[x]=1;
for(int i=head[x];i;i=nextt[i]){
if(!dfn[to[i]]){
tarjan(to[i]);
low[x]=min(low[x],low[to[i]]);
}
else if(ins[to[i]])low[x]=min(low[x],dfn[to[i]]);
}
if(dfn[x]==low[x]){
cnt++; int y;
do{
y=s[top--],ins[y]=0;
c[y]=cnt,scc[cnt].push_back(y);
}while(x!=y);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
while(scanf("%d",&x),x){
add(i,x);
}
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
//缩点
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=nextt[i]){
int y=to[i];
if(c[x]==c[y])continue;
add_c(c[x],c[y]);
}
}
return 0;
}
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3e5+10;
int n,m,dfs_clock,dfn[N],rev[N],f[N]; //点的dfs序,dfs对应的点,父亲结点
int semi[N],idom[N],Ans[N]; //半支配点,支配点,答案
struct Node{int to,next;};
struct Graph{ //树
int tot,head[N];
Node E[N];
inline void clear() {
tot=0;
for(int i=0;i<=n;++i) head[i]=0;
}
inline void link(int u,int v) {
E[++tot]=(Node){v,head[u]}; head[u]=tot;
}
}pre,nxt,dom; //nxt原树,pre反树,dom支配树
struct uset{ //并查集
int fa[N],Mi[N];
inline void init() {
for(int i=1;i<=n;++i)
fa[i]=Mi[i]=semi[i]=i;
}
inline int find(int x){
if(fa[x]==x)return x;
int fx=fa[x],y=find(fa[x]);
if(dfn[semi[Mi[fx]]]<dfn[semi[Mi[x]]])Mi[x]=Mi[fx];
return fa[x]=y;
}
}uset;
inline void dfs(int x) { //先dfs一遍计算dfn,rev,father数组
dfn[x]=++dfs_clock;rev[dfs_clock]=x;
for(int e=nxt.head[x];e;e=nxt.E[e].next){
if(!dfn[nxt.E[e].to])
f[nxt.E[e].to]=x,dfs(nxt.E[e].to);
}
}
inline void getans(int x) { //计算答案,每个点被多少个点支配
Ans[x]=1;
for(int e=dom.head[x];e;e=dom.E[e].next) {
getans(dom.E[e].to);
Ans[x]+=Ans[dom.E[e].to];
}
}
inline void calc() { //构建支配树
for(int i=n;i>=2;--i) { //从dfs序大的点开始
int y=rev[i],tmp=n;
for(int e=pre.head[y];e;e=pre.E[e].next) { //所有能到达y点的边
int x=pre.E[e].to; // (x,y)
if (!dfn[x]) continue;
if (dfn[x]<dfn[y]) tmp=min(tmp,dfn[x]);
else uset.find(x),tmp=min(tmp,dfn[semi[uset.Mi[x]]]);
}
semi[y]=rev[tmp];uset.fa[y]=f[y];
dom.link(semi[y],y);
y=rev[i-1];
for (int e=dom.head[y];e;e=dom.E[e].next) {
int x=dom.E[e].to; uset.find(x);
if (semi[uset.Mi[x]]==y) idom[x]=y;
else idom[x]=uset.Mi[x];
}
}
for(int i=2;i<=n;++i){
int x=rev[i];
if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
}
dom.clear();
for(int i=2;i<=n;++i) dom.link(idom[i],i); //2-n点连接支配树
getans(1); //计算答案
for(int i=1;i<=n;++i) {
printf("%d",Ans[i]),Ans[i]=0;
i==n?printf("\n"):printf(" ");
}
}
//P5180支配树模板 起点为1的有向图 求每个点能支配的点的个数(包括自己)
int main() {
scanf("%d%d",&n,&m);
dfs_clock=0; pre.clear(); nxt.clear(); dom.clear();
for(int i=1;i<=n;++i) dfn[i]=rev[i]=semi[i]=idom[i]=f[i]=0;
for(int i=1;i<=m;++i) {
int u,v; scanf("%d%d",&u,&v);
nxt.link(u,v);
pre.link(v,u);
}
dfs(1);
uset.init();
calc();
return 0;
}
string add(string s1,string s2) {
int len1 = s1.size(), len2 = s2.size();
if (len1 < len2)swap(s1,s2);
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
int len = max(len1,len2);
string ans;
ans.resize(len);
int sum = 0;
for (int i = 0; i < min(len1, len2); i++) {
int k = sum + (s1[i] - '0') + (s2[i] - '0');
ans[i] = k % 10+'0';
sum = k / 10;
}
for (int i = min(len1, len2); i < len; i++) {
int k = sum + (s1[i] - '0');
ans[i] = k % 10 + '0';
sum = k / 10;
}
if (sum)ans.insert(ans.begin(),'0'+sum);
reverse(ans.begin(),ans.end());
return ans;
}
string reduce(string s1, string s2) { //保证s1>=s2;
int len1 = s1.size(),len2=s2.size();
reverse(s1.begin(), s1.end()); reverse(s2.begin(),s2.end());
string ans; ans.resize(len1);
int re = 0;
for (int i = 0; i < len2; i++) {
int a = s1[i] - '0',b=s2[i]-'0';
a -= re;
re = 0;
if (a < b) {
a += 10; re++;
}
ans[i] = a - b + '0';
}
for (int i = len2; i < len1; i++) {
int a = s1[i] - '0';
a -= re;
re = 0;
if (a < 0) {
a += 10;
re++;
}
ans[i] = a + '0';
}
for (int i = len1 - 1; i >= 0; i--) {
if (ans[i] != '0')break;
ans.erase(ans.end()-1);
}
reverse(ans.begin(), ans.end());
if (ans.size() == 0)ans.insert(ans.begin(),'0');
return ans;
}
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 200 * 100 + 10;
const int M = 400 * 100 + 10;
int n;
int sz, mx, rt,ans;
int head[N], to[M], len[M], ne[M], cnt;
int dis[N], siz[N],vis[N],num[2020];
void add(int x, int y, int w) {
to[++cnt] = y, len[cnt] = w, ne[cnt] = head[x], head[x] = cnt;
}
int getrt(int x, int f) {
siz[x] = 1;
int ans = 0;
for (int i = head[x],y; i; i = ne[i]) {
y = to[i];
if (y == f || vis[y])continue;
siz[x] += getrt(y,x);
ans = max(ans,siz[y]);
}
ans = max(ans,sz-siz[x]);
if (ans < mx) {
mx = ans;
rt = x;
}
return siz[x];
}
void getdis(int x, int f) {
num[dis[x] % 2019]++;
for (int i = head[x],y; i; i = ne[i]) {
y = to[i];
if (y == f || vis[y])continue;
dis[y] = (dis[x] + len[i]) % 2019;
getdis(y,x);
}
}
int solve(int x, int ds) {
memset(num, 0, sizeof(num));
dis[x] = ds % 2019;
getdis(x,0);
int ans = num[0] * (num[0] - 1) / 2;
for (int i = 1; i <= 2019 / 2; i++) {
ans += num[i] * num[2019 - i];
}
return ans;
}
void dfs(int x) {
ans += solve(x,0);
vis[x] = 1;
for (int i = head[x],y; i; i = ne[i]) {
y = to[i];
if (vis[y])continue;
ans -= solve(y, len[i]);
mx = INF;
sz = siz[y];
getrt(y,0);
dfs(rt);
}
}
int main() {
while (scanf("%d", &n) == 1) {
for (int i = 1; i <= n; i++)head[i] = dis[i] = vis[i] = 0;
ans = 0; cnt = 1;
for (int i = 1, x, y, w; i < n; i++) {
scanf("%d%d%d",&x,&y,&w);
add(x, y, w); add(y, x, w);
}
sz = n; mx = INF;
getrt(1,0);
dfs(rt);
printf("%d\n",ans);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 5010, M = 100000+10;
int ver[M], edge[M], cost[M], ne[M], head[N];
int d[N], incf[N], pre[N], v[N];
int n, k, m,tot, s, t, maxflow, ans;
void add(int x, int y, int z, int c) {
ver[++tot] = y, edge[tot] = z, cost[tot] = c, ne[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, cost[tot] = -c, ne[tot] = head[y], head[y] = tot;
}
int num(int i, int j, int k) {
return (i - 1)*n + j + k * n*n;
}
//最小费用跑最短路,最大费用跑最长路;
bool spfa() {
queue<int>q;
memset(d, 0x3f, sizeof(d));
//memset(d, 0xcf, sizeof(d)); 负无穷
memset(v, 0, sizeof(v));
q.push(s); d[s] = 0, v[s] = 1;
incf[s] = 1 << 30;
while (q.size()) {
int x = q.front(); v[x] = 0; q.pop();
for (int i = head[x]; i; i = ne[i]) {
if (!edge[i])continue;
int y = ver[i];
if (d[y] > d[x] + cost[i]) {
d[y] = d[x] + cost[i];
incf[y] = min(incf[x], edge[i]);
pre[y] = i;
if (!v[y])v[y] = 1, q.push(y);
}
}
}
if (d[t] == 0x3f3f3f3f)return false;
return true;
}
void update() {
int x = t;
while (x != s) {
int i = pre[x];
edge[i] -= incf[t];
ans += incf[t] * cost[i];
edge[i ^ 1] += incf[t];
x = ver[i ^ 1];
}
maxflow += incf[t];
}
int main() {
cin >> n >> m >> s >> t;
tot = 1;
for (int i = 1; i <= m; i++) {
int x, y, c, w;
scanf("%d%d%d%d",&x,&y,&c,&w);
add(x,y,c,w);
}
while (spfa())update();
cout <<maxflow<<" "<< ans << endl;
return 0;
}
文章浏览阅读2.5w次,点赞6次,收藏50次。官方解释是,docker 容器是机器上的沙盒进程,它与主机上的所有其他进程隔离。所以容器只是操作系统中被隔离开来的一个进程,所谓的容器化,其实也只是对操作系统进行欺骗的一种语法糖。_docker菜鸟教程
文章浏览阅读5.7k次,点赞3次,收藏14次。该如何避免的,今天小编给大家推荐两个下载Windows系统官方软件的资源网站,可以杜绝软件捆绑等行为。该站提供了丰富的Windows官方技术资源,比较重要的有MSDN技术资源文档库、官方工具和资源、应用程序、开发人员工具(Visual Studio 、SQLServer等等)、系统镜像、设计人员工具等。总的来说,这两个都是非常优秀的Windows系统镜像资源站,提供了丰富的Windows系统镜像资源,并且保证了资源的纯净和安全性,有需要的朋友可以去了解一下。这个非常实用的资源网站的创建者是国内的一个网友。_msdn我告诉你
文章浏览阅读1.2k次。vue2封装对话框el-dialog组件_
文章浏览阅读4.7k次,点赞5次,收藏6次。MFC 文本框换行 标签: it mfc 文本框1.将Multiline属性设置为True2.换行是使用"\r\n" (宽字符串为L"\r\n")3.如果需要编辑并且按Enter键换行,还要将 Want Return 设置为 True4.如果需要垂直滚动条的话将Vertical Scroll属性设置为True,需要水平滚动条的话将Horizontal Scroll属性设_c++ mfc同一框内输入二行怎么换行
文章浏览阅读832次。检查Linux是否是否开启所需端口,默认为6379,若未打开,将其开启:以root用户执行iptables -I INPUT -p tcp --dport 6379 -j ACCEPT如果还是未能解决,修改redis.conf,修改主机地址:bind 192.168.85.**;然后使用该配置文件,重新启动Redis服务./redis-server redis.conf..._redis-server doesn't support auth command or ismisconfigured. try
文章浏览阅读4.9k次。济大数电实验报告_数据选择器及其应用
文章浏览阅读236次。1研究内容消费在生产中占据十分重要的地位,是生产的最终目的和动力,是保持省内经济稳定快速发展的核心要素。预测河南省社会消费品零售总额,是进行宏观经济调控和消费体制改变创新的基础,是河南省内人民对美好的全面和谐社会的追求的要求,保持河南省经济稳定和可持续发展具有重要意义。本文建立灰色预测模型,利用MATLAB软件,预测出2019年~2023年河南省社会消费品零售总额预测值分别为21881...._灰色预测模型用什么软件
文章浏览阅读1.2k次。12.4-在Qt中使用Log4Qt输出Log文件,看这一篇就足够了一、为啥要使用第三方Log库,而不用平台自带的Log库二、Log4j系列库的功能介绍与基本概念三、Log4Qt库的基本介绍四、将Log4qt组装成为一个单独模块五、使用配置文件的方式配置Log4Qt六、使用代码的方式配置Log4Qt七、在Qt工程中引入Log4Qt库模块的方法八、获取示例中的源代码一、为啥要使用第三方Log库,而不用平台自带的Log库首先要说明的是,在平时开发和调试中开发平台自带的“打印输出”已经足够了。但_log4qt
文章浏览阅读786次。全局观思维模型,一个教我们由点到线,由线到面,再由面到体,不断的放大格局去思考问题的思维模型。_计算机中对于全局观的
文章浏览阅读330次。一、CountDownLatch介绍CountDownLatch采用减法计算;是一个同步辅助工具类和CyclicBarrier类功能类似,允许一个或多个线程等待,直到在其他线程中执行的一组操作完成。二、CountDownLatch俩种应用场景: 场景一:所有线程在等待开始信号(startSignal.await()),主流程发出开始信号通知,既执行startSignal.countDown()方法后;所有线程才开始执行;每个线程执行完发出做完信号,既执行do..._countdownluach于cyclicbarrier的用法
文章浏览阅读508次。Prometheus 算是一个全能型选手,原生支持容器监控,当然监控传统应用也不是吃干饭的,所以就是容器和非容器他都支持,所有的监控系统都具备这个流程,_-自动化监控系统prometheus&grafana实战
文章浏览阅读4.7k次。输入关键字,可以通过键盘的搜索按钮完成搜索功能。_react search