代码仓库

26

代码仓库

if((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue; e.flow += f;

edges[G[x][i]^1].flow-=f;//?? flow+=f; a-=f; if(a==0)break; }

return flow; }

inlineint maxflow(){return Maxflow(s,t);} inlineint Maxflow(constint& s,constint& t){ int flow=0;

memset(ans,0,sizeof(ans)); while(BFS()){

memset(cur,0,sizeof(cur)); int f = DFS(s,INF); flow += f ; }

for(int i=0;i

ans[e.from][e.to-n]+=e.flow; }

return flow; }

inlinevoid Init(){ s =0, t = n+m+1; edges.clear();

for(int i=0;i<=m+n+1;i++) G[i].clear(); for(int i=1;i<=n;i++) AddEdge( s ,i,a[i]); for(int i=1;i<=m;i++) AddEdge(i+n,t,b[i]); for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)AddEdge(i,j+n,19); } }g;

Truck最大生成树+LCA

#include #include #include 27

代码仓库

#include #include usingnamespace std; constint INF=0x3f3f3f3f; constint N =1e5+5; int n,m;

struct gragh{ struct Edge{ int from,to,w; Edge(){}

Edge(int x,int y,int z):from(x),to(y),w(z){} booloperator<(const Edge& a)const{ return w < a.w; }

}edges[N],be[N];

int E,f[N],fa[N][20],di[N][20],dep[N]; bool vis[N];

vectorG[N];

int F(int x){//鼯

return f[x]==x?x:(f[x]=F(f[x])); }

inlinevoid link(int x,int y,int z){ edges[++E]=Edge(x,y,z); G[x].push_back(E); }

void build(){ E=0;

for(int i=1;i<=n;i++)G[i].clear(); int x,y,z;

for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++){

scanf(\,&x,&y,&z); be[i]=Edge(x,y,z); f[F(x)]=F(y); } }

void kruskal(){

int treenum =0;//forests

28

代码仓库

memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)if(!vis[F(i)]){ treenum++;vis[F(i)]=1; }

for(int i=1;i<=n;i++)f[i]=i; sort(be+1,be+m+1); int cnt =0;

for(int i=m;i>=1;i--){ int x = be[i].from; int y = be[i].to ; if(F(x)==F(y))continue; f[F(x)]=F(y); cnt++;

link(x,y,be[i].w); link(y,x,be[i].w); if(cnt==n-treenum)break; } }

void dfs(int x){ vis[x]=1;

for(int i=1;i<=17;i++){ if(dep[x]<(1<

fa[x][i]=fa[fa[x][i-1]][i-1];

di[x][i]=min(di[x][i-1],di[fa[x][i-1]][i-1]); }

for(int i=0;i

int lca(int x,int y){ if(dep[x]=0;i--)

29

代码仓库

if(fa[x][i]!=fa[y][i]){

x=fa[x][i];y=fa[y][i]; }

if(x==y)return x; return fa[x][0]; }

int ask(int x,int f){//f:father int ans = INF;

int t = dep[x]-dep[f];

for(int i=0;i<=17;i++)if(t&(1<

return ans; }

void work(){ build(); kruskal();

memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)if(!vis[i])dfs(i); int q,x,y;

scanf(\,&q); while(q--){

scanf(\,&x,&y); if(F(x)!=F(y))puts(\); else{

int t = lca(x,y);

x = ask(x,t); y = ask(y,t);

printf(\,min(x,y)); } } } }g;

int main(){

//freopen(\//freopen(\for(;~scanf(\,&n,&m);)g.work(); return0;

30

代码仓库

} 背包

#include #include #include usingnamespace std; constint N =100007; struct node { int v,w,n; node(){}

node(int x,int y,int z){ v=x,w=y,n=z; } }a[N];

int f[N]; int main(){

//freopen(\int cash,n,x,y;

for(;~scanf(\,&cash,&n);){ int A =0;

for(int i=1;i<=n;i++){

scanf(\,&x,&y); for(int t=0;(1<

a[++A]=node(y*tt,y*tt,1); x -= tt; }

if(x)a[++A]=node(y*x,y*x,1); }

memset(f,0,sizeof(f));//01背包 for(int i=1;i<=A;i++)

for(int j=cash;j>=a[i].v;j--)

f[j]=max(f[j],f[j-a[i].v]+a[i].w);