专项测试 图论1
T1 序列
分块，对每个块重新排序，区间取max就块内二分出能更新到的右端点，然后存一个栈里
为了防止MLE可以在栈内元素超过\(O(\sqrt n)\)时pushdown
修改时的散块和查询时所在的块都要先pushdown
散块修改后重构一下
复杂度\(O(n\sqrt n\log n)\)
坑：当加的数是0时不能算作一次变化
T2 旅行计划
若u，v不在一个联通块里，NIE
若k为奇数，可以u，v之间来回走，答案一定是0
若k为偶数，对于联通块内所有边l1,l2,...,le,使d=gcd(l1,l2,...,le,k)，先使所有数除以d，此时存在
\[k_1l_1+k_2l_2+...+k_el_e \equiv1 \pmod k \]因为每条边可以来回走，那么从任意一点出发都可以经过所有边两次回到自身(dfs树)，也就是存在模k意义下为2的环
那么若存在一条u->v的偶数路径，可以一直跑环直到k的倍数，答案是0
若只存在u->v的奇数路径，跑环直到\(a* k-1\)，再跑一遍变成\(a* k+1\)，然后答案就是1* d
所以问题转换成了寻找偶数路径
偶数路径可以是奇环加奇数路径，或一条简单偶数路径
每个点拆成奇点和偶点，并查集维护，u->v为奇就奇点连偶点，否则偶连偶，奇连奇
若满足条件那么u，v的奇点在同一并查集里
T3 hack
限制是每条路径上只能割一条边
缩成DAG后建出0->n-1的分层图，不难发现若没有层间边和反向边，直接跑最小割就是答案
若u->v是一条层间边或反向边，s->u和v->t一定不能同时被割
连一条v->u的inf边即可
坑：不保证联通，缩点之后建边0会乱连
代码
T1
#include
using namespace std;
#define il inline
#define int long long
const int inf=1e15;
const int N=1e5+11;
const int siz=201;
struct opt_{int r;int val;}opt[511][511];
struct loc_{
int val;
int num,id;
friend bool operator<(loc_ a,loc_ b){return a.val'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
il char readc()
{
char ch=getchar();
while(ch!='Q'&&ch!='A'&&ch!='M') ch=getchar();
return ch;
}
void pushdown(int &x)
{
if(!top[x]) return;
int num=0;
int i;
int val=opt[x][top[x]].val;
while(top[x])
{
++num;
for(i=opt[x][top[x]].r;i>opt[x][top[x]-1].r;--i) a[i].val=val,a[i].num+=num;
--top[x];
}
return;
}
void add(int &l,int &r,int &val)
{
if(val==0) return;
int i;
int bl=blo[l],br=blo[r];
if(bl==br)
{
pushdown(bl);
for(i=lb[bl];i<=rb[bl];++i) if(a[i].id>=l&&a[i].id<=r) a[i].val+=val,++a[i].num;
sort(a+lb[bl],a+rb[bl]+1);
return;
}
pushdown(bl),pushdown(br);
for(i=lb[bl];i<=rb[bl];++i) if(a[i].id>=l&&a[i].id<=r) a[i].val+=val,++a[i].num;
for(i=lb[br];i<=rb[br];++i) if(a[i].id>=l&&a[i].id<=r) a[i].val+=val,++a[i].num;
sort(a+lb[bl],a+rb[bl]+1);
sort(a+lb[br],a+rb[br]+1);
for(i=bl+1;i400) pushdown(i);
if(opt[i][top[i]].val+delv[i]>=val) return;
int l=opt[i][top[i]].r+1,r=rb[i],mid,ans=opt[i][top[i]].r;
while(l<=r)
{
mid=(l+r)>>1;
if(a[mid].val+delv[i]=l&&a[i].id<=r&&a[i].val+delv[bl]=l&&a[i].id<=r&&a[i].val+delv[bl]=l&&a[i].id<=r&&a[i].val+delv[br] T2
#include
using namespace std;
const int N=2e5+11;
int n,m,q;
int f[N],f1[N];
int u[N],v[N],w[N];
int gd[N];
int find(int x){if(x==f[x])return x;return f[x]=find(f[x]);}
int find1(int x){if(x==f1[x])return x;return f1[x]=find1(f1[x]);}
int gcd(int x,int y){if(!y)return x;return gcd(y,x%y);}
void merge(int x,int y){x=find(x),y=find(y);f[x]=y;gd[y]=gcd(gd[y],gd[x]);return;}
void mergej(int x,int y){f1[find1(x+n)]=find1(y),f1[find1(x)]=find1(y+n);return;}
void mergeo(int x,int y){f1[find1(x)]=find1(y),f1[find1(x+n)]=find1(y+n);return;}
inline int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
int main()
{
n=read();
m=read();
q=read();
for(int i=1;i<=n;++i) f[i]=f1[i]=i,f1[i+n]=n+i;
for(int x,i=1;i<=m;++i)
{
u[i]=read(),v[i]=read(),w[i]=read();
merge(u[i],v[i]);
x=find(u[i]);
if(gd[x]) gd[x]=gcd(gd[x],w[i]);
else gd[x]=w[i];
}
for(int x,y,z,i=1;i<=m;++i)
{
x=u[i],y=v[i],z=w[i]/gd[find(x)];
if(z&1) mergej(x,y);
else mergeo(x,y);
}
for(int x,y,k,i=1;i<=q;++i)
{
x=read(),y=read(),k=read();
if(find(x)!=find(y)) printf("%s\n","NIE");
else if(find1(x)==find1(y)) printf("%d\n",0);
else printf("%d\n",gcd(k,gd[f[x]]));
}
return 0;
}
T3
#include
using namespace std;
#define il inline
#define int long long
const int N=1e4+11;
const int inf=0x7fffffff;
struct qxxx{int v,next,w;}cc[N];
struct e_{int u,v,w;}e[N];
bool vis[N];
int n,m,s,t;
int d[N];
int dfn[N],st,low[N],f[N],num;
int first[N],cnt,now[N];
stack sta;
queue dui;
il int min_(int x,int y){return x>y?y:x;}
il void qxx(int u,int v,int w){cc[++cnt]={v,first[u],w};first[u]=cnt;return;}
il void add(int u,int v,int w){qxx(u,v,w),qxx(v,u,0);return;}
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void tarjan(int x)
{
vis[x]=1;
sta.push(x);
low[x]=dfn[x]=++st;
for(int i=first[x];i;i=cc[i].next)
{
if(!dfn[cc[i].v])
{
tarjan(cc[i].v);
low[x]=min_(low[x],low[cc[i].v]);
}
else if(vis[cc[i].v]) low[x]=min_(low[x],dfn[cc[i].v]);
}
if(low[x]==dfn[x])
{
int tmp;
++num;
do{
tmp=sta.top();
sta.pop();
f[tmp]=num;
vis[tmp]=0;
}while(tmp!=x);
}
return;
}
bool bfs()
{
while(dui.size())dui.pop();
memset(d,0,sizeof(d));
d[s]=1;
now[s]=first[s];
int x;
dui.push(s);
while(dui.size())
{
x=dui.front(),dui.pop();
for(int i=first[x];i;i=cc[i].next)
if(cc[i].w&&!d[cc[i].v])
{
d[cc[i].v]=d[x]+1;
now[cc[i].v]=first[cc[i].v];
dui.push(cc[i].v);
if(cc[i].v==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int rest=flow,i,k;
for(i=now[x];i;i=now[x]=cc[i].next)
{
if(cc[i].w&&d[cc[i].v]==d[x]+1)
{
k=dinic(cc[i].v,min_(rest,cc[i].w));
if(!k) d[cc[i].v]=0;
rest-=k;
cc[i].w-=k;
cc[i^1].w+=k;
}
if(!rest) break;
}
return flow-rest;
}
signed main()
{
n=read(),m=read();
for(int x,y,z,i=1;i<=m;++i)
{
x=read(),y=read(),z=read();
e[i]={x,y,z};
qxx(x,y,z);
}
tarjan(0);
if(f[0]==f[n-1]){cout<<-1<d[f[y]]) add(f[y],f[x],inf);
}
int maxflow=0,flow;
while(bfs())while(flow=dinic(s,inf))maxflow+=flow;
cout<