reshuffle

#include<iostream>//P3387,拓扑排序加强连通分量tarjan
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define maxn 400010
#define INF 1e18
int low[maxn],dfn[maxn],d[maxn],sta[maxn],dis[maxn],fa[maxn];
int ne[maxn],u[maxn],v[maxn],fi[maxn],l[maxn],r[maxn],ru[maxn];
int f[maxn];
bool omit[maxn];
int n,m,t,top,times,tot;
int ans;
void edge(int x,int y)
{
	t++;
	ne[t]=fi[x];
	fi[x]=t;
	u[t]=x;
	v[t]=y;
}

void scc(int now)//strongly connectly component
{
	times++;
	dfn[now]=low[now]=times;
	top++;
	sta[top]=now;
	omit[now]=0;
	for (int i=fi[now];i!=-1;i=ne[i])
	{
		if (!dfn[v[i]])
		{
			scc(v[i]);
			low[now]=min(low[now],low[v[i]]);
		}
		else if (!omit[v[i]])
		{
			if (dfn[v[i]]<low[now]) low[now]=dfn[v[i]];
		}
	}
	if (low[now]==dfn[now])
	{
		tot++;
		do
		{		
			dis[tot]+=d[sta[top]];
			fa[sta[top]]=tot; 
			omit[sta[top]]=1;
			top--;
		}
		while (sta[top+1]!=now);
	}
}

void tuopu()//tuopu sort + DAG dp
{
	queue<int>q;
	for (int i=1;i<=tot;i++) if (!ru[i]) q.push(i);
	while (!q.empty())
	{
		int k=q.front();
		q.pop();
		for (int i=fi[k];i!=-1;i=ne[i])
		{
			int next=v[i];
			ru[next]--;
			f[next]=max(f[next],f[k]+dis[next]);////////WA.equation lies in here!
			if (!ru[next]) q.push(next);
				
		
		}
	}
}


int main()
{

	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&d[i]);
	
	t=0;
	top=0;
	memset(dis,0,sizeof(dis));	
	memset(low,0,sizeof(low));
	for (int i=1;i<=n;i++) fi[i]=-1;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		l[i]=x;
		r[i]=y;
		edge(x,y);
	}
	for (int i=1;i<=n;i++) 
		if (!dfn[i]) scc(i);
		
	//rebuild	
	for (int i=1;i<=n;i++) fi[i]=-1;
	t=0;	
	for (int i=1;i<=m;i++)
	{
		if (fa[l[i]]!=fa[r[i]])
		{
			edge(fa[l[i]],fa[r[i]]);
			ru[fa[r[i]]]++;
		}
	}
	
	//DP
	for (int i=1;i<=tot;i++)f[i]=dis[i];
	tuopu();


	for (int i=1;i<=tot;i++) ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}

#include<cstdio>//费用流加离散化
#include<queue>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=400010;
int ne[maxn],fi[maxn],u[maxn],v[maxn],w[maxn],f[maxn];//f value    w flow
bool ff[maxn];
int pr[maxn],pre[maxn],dis[maxn],flow[maxn],psi[maxn],an[maxn];
int a[maxn],b[maxn],c[maxn];
int cmp,l[maxn],r[maxn];
int ans,di,t=-1,tt,n,m,sta,aim;// t=    -1
int maxflow,minval;


const int d[8][2] = 
{//待会枚举四个方向用的 
    {2,1},
    {2,-1},
    {-2,1},
    {-2,-1},
    {1,2},
    {-1,2},
    {1,-2},
    {-1,-2}
};

void edge(int x,int y,int z,int c)
{
	t++;
	ne[t]=fi[x];
	fi[x]=t;
	u[t]=x;
	v[t]=y;
	w[t]=z;	
	f[t]=c;
	t++;
	ne[t]=fi[y];
	fi[y]=t;
	u[t]=y;
	v[t]=x;
	w[t]=0;  
	f[t]=-c;
}
bool bfs()
{
	memset(dis,127,sizeof(dis));
    memset(flow,127,sizeof(flow));
    memset(ff,0,sizeof(ff));
	queue<int>q;
	while (!q.empty()) q.pop();
	q.push(sta);
	dis[sta]=0;
	pre[aim]=-1;	
	while (!q.empty())
	{
		int now=q.front();		
		q.pop();
		ff[now]=0;	
		for (int i=fi[now];i!=-1;i=ne[i]) if ((dis[now]+f[i]<dis[v[i]])&&(w[i]>0)) 
		{
			dis[v[i]]=dis[now]+f[i];
			pre[v[i]]=now;
			pr[v[i]]=i;		
			flow[v[i]]=min(flow[now],w[i]);
			if (!ff[v[i]])
			{
				q.push(v[i]);
				ff[v[i]]=1;
			}			
		}		
	}
	if (pre[aim]==-1) return 0;else return 1;
}

int main()
{

	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if (x>y) swap(x,y);
		a[i*2-1]=x,a[i*2]=y;
		l[i]=x,r[i]=y;
		c[i]=y-x;		
	}
	sort(a+1,a+1+n*2);
	cmp=unique(a+1,a+1+n*2)-a-1;
//	for (int i=1;i<=cmp+1;i++) cout<<i<<a[i]<<endl;
//	cout<<cmp;
	
	

	sta=0,aim=cmp+1;
	for (int i=sta;i<=aim;i++) fi[i]=-1;
	
	for (int i=1;i<=n;i++)
	{
		int xx=lower_bound(a+1,a+1+cmp,l[i])-a;//we dont minus additional one here, i dont know why
		int yy=lower_bound(a+1,a+1+cmp,r[i])-a;
		edge(xx,yy,1,-c[i]);
	}
	for (int i=1;i<cmp;i++) edge(i,i+1,maxn,0);
	edge(sta,1,m,0);edge(cmp,aim,m,0);
	
/*	for (int i=1;i<=n;i++) edge(i*2-1,i*2,1,-c[i]);
	for (int i=1;i<2*n;i++) edge(b[i],b[i+1],maxn,0);
	edge(sta,1,m,0);edge(2*n,aim,m,0);
	for (int i=1;i<=2*n;i++)
	for (int j=1;j<=i-1;j++)
	{
		if (a[b[j]]==a[b[i]]) edge(b[i],b[j],maxn,0),edge(b[j],b[i],maxn,0);
	}*/
//for (int i=1;i<=n*2;i++) cout<<b[i]<<endl;return 0;

	
//	for (int i=0;i<=t;i++)	printf("%d %d %d %d %d
",i,u[i],v[i],w[i],f[i]);
//	return 0;
	while (bfs())	
	{
		maxflow+=flow[aim];
		minval+=dis[aim]*flow[aim];
		int now=aim;				
		while (now!=sta)
		{
			w[pr[now]]-=flow[aim];
			w[pr[now]^1]+=flow[aim];
			now=pre[now];
		}	
	}	
	
	cout<<-minval;
	
}

---

#include<cstdio>///////////P2762网络流24题飞行计划：dicnic 
#include<queue>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<string>
using namespace std;
const int maxn=400010;
int ne[maxn],fi[maxn],u[maxn],v[maxn],w[maxn],d[maxn],f[maxn];//f value    w flow
int ans,di,t=-1,tt,n,m,sta,aim;// t=    -1
int maxflow,minval;
int an[maxn];
void edge(int x,int y,int z,int c)
{
	t++;
	ne[t]=fi[x];
	fi[x]=t;
	u[t]=x;
	v[t]=y;
	w[t]=z;	
	f[t]=c;
	t++;
	ne[t]=fi[y];
	fi[y]=t;
	u[t]=y;
	v[t]=x;
	w[t]=0;    //  w[t]==0
	f[t]=-c;
}
bool bfs()
{
	memset(d,0,sizeof(d));
	queue<int>q;
	q.push(sta);
	d[sta]=1;
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=fi[now];i!=-1;i=ne[i]) if ((w[i]>0)&&(d[v[i]]==0)) 
		{
			q.push(v[i]);
			d[v[i]]=1+d[now];			
		}		
	}
	if (d[aim]!=0) return 1;
	return 0;
}
int dfs(int now,int flow)
{
//	cout<<now;
	if (now==aim) return flow;
	int sum=0;
	for (int i=fi[now];i!=-1;i=ne[i]) if ((w[i]>0)&&(d[v[i]]==d[now]+1))
	{
		int delta=dfs(v[i],min(flow-sum,w[i]));
		if (!delta) continue;
		w[i]-=delta;
		w[i^1]+=delta;
		sum+=delta;
		if (sum==flow) break;		
	} 
	
	if (sum==0) d[now]=0;
	if (sum==flow) d[now]=0;	
	return sum;
}
int main()
{
		cin>>m>>n;
		sta=0,aim=m+n+1;
		for (int i=sta;i<=aim;i++) fi[i]=-1;
		char c;c=getchar();//
		for (int i=1;i<=m;i++)
		{
			string s;
			getline(cin,s);
			stringstream ss;
			ss<<s;
			int x,y;			
			ss>>x;
			ans+=x;
			edge(sta,i,x,0);
			while (ss>>y)
			{
				edge(i,y+m,maxn,0);
//				cout<<y<<endl;
			}
		}
		for (int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			edge(i+m,aim,x,0);
		}


//printf("%d %d
",0,v[fi[0]]);
	
//	for (int i=0;i<=t;i++)	printf("%d %d %d %d %d
",i,u[i],v[i],w[i],f[i]);
	//return 0;
//	for (int i=0;i<=aim;i++) printf("%d %d
",i,v[fi[i]]);
	
	while (bfs())	
	{		
//		for (int i=1;i<=n+m;i++) printf("%d %d
",i,d[i]);return 0;
		maxflow+=dfs(sta,maxn);
	}	
	for (int i=0;i<=t;i++) if ((u[i]==0)&&(w[i]>0)) an[++tt]=v[i];
	for (int i=1;i<=tt;i++) printf("%d ",an[i]);
	cout<<endl;
	tt=0;
	for (int i=0;i<=t;i++) if ((v[i]==aim)&&(w[i]==0)) an[++tt]=u[i]-m;
	for (int i=1;i<=tt;i++) printf("%d ",an[i]);	
	cout<<endl;
	cout<<ans-maxflow;	
	cin>>n;
	return 0;

	
}

---

#pragma comment(linker, "/STACK:1024000000,1024000000") //HDU 5692 线段树
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 400010
#define INF 1e18
struct re
{
	int x,y,rz;
	long long z;
};
re f[maxn];

int fi[maxn],ne[maxn],u[maxn],v[maxn];
bool vis[maxn];
int t=0,step=0;
int a[maxn];
long long d[maxn];
int data[maxn];
int l[maxn],r[maxn];

long long max(long long a,long long b)
{
	if (a>b) return a;else return b;
}
void edge(int x,int y)
{
	t++;
	ne[t]=fi[x];
	fi[x]=t;
	u[t]=x;
	v[t]=y;
	t++;
	ne[t]=fi[y];
	fi[y]=t;
	u[t]=y;
	v[t]=x;
}
void dfs(int now)
{
	step++;
	a[step]=now;
	l[now]=step;
	vis[now]=1;
	for (int i=fi[now];i!=-1;i=ne[i]) if (!vis[v[i]])
	{
		int next=v[i];
		d[next]+=d[now];
		dfs(next);
	}
	r[now]=step;
	return;
}




void down(int k)
{
	f[k*2].rz+=f[k].rz;
	f[k*2].z+=f[k].rz;
	
	f[k*2+1].rz+=f[k].rz;
	f[k*2+1].z+=f[k].rz;	
	
	f[k].rz=0;
	return;
}


void up(int k)
{
	f[k].z=max(f[k*2].z,f[k*2+1].z);
	return;
}

void update(int k,int l,int r,int zd)
{	
	if ((f[k].x>r)||(f[k].y<l)) return;
	if ((f[k].x>=l)&&(f[k].y<=r))
	{
		f[k].rz+=zd;
		f[k].z+=zd;
//		int i=k; printf("%d %d      %d %d %lf %d
",l,r,f[i].x,f[i].y,f[i].z,f[i].rz);
		return;
	}		
	
	down(k);
	update(k*2,l,r,zd);
	update(k*2+1,l,r,zd);		
	
	up(k);
//	int i=k; printf("%d %d      %d %d %lf %d
",l,r,f[i].x,f[i].y,f[i].z,f[i].rz);
	return;
}

long long inquiry(int k,int l,int r)
{	

//	printf("%d %d      %d %d %lld
",l,r,f[k].x,f[k].y,f[k].z);
	
	if ((f[k].x>r)||(f[k].y<l)) return -INF;
	if ((f[k].x>=l)&&(f[k].y<=r))
	{
		return f[k].z;
	}			
	down(k);
	long long aa=inquiry(k*2,l,r);
	long long bb=inquiry(k*2+1,l,r);	
	return max(aa,bb);

}

void build(int k,int l,int r)
{
	f[k].x=l;
	f[k].y=r;
	if (l==r)
	{
		f[k].z=d[a[l]];
		f[k].rz=0;
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	up(k);
	return;
}

int main()
{
	int turn;
	cin>>turn;
	int kase=0;
	while (turn--)
	{
		
		printf("Case #%d:
",++kase);
				
		t=0,step=0;
		
		int n,m;
		cin>>n>>m;
		for (int i=0;i<=n;i++) fi[i]=-1;
		for (int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			edge(x,y);
		}
		for (int i=0;i<n;i++)
		{
			scanf("%d",&data[i]);
			d[i]=data[i];
		}
		memset(vis,0,sizeof(vis));
		dfs(0);
//		for (int i=0;i<n;i++) printf("%d %d %d %d
",i,l[i],r[i],d[i]);
			
		build(1,1,n);
//		for (int i=1;i<=15;i++) printf("%d %d %d %lld
",i,f[i].x,f[i].y,f[i].z);
		
		

		for (int i=1;i<=m;i++)
		{
			int qwe;
			scanf("%d",&qwe);
			if (qwe==1)
			{
				int xx;
				scanf("%d",&xx);
				printf("%lld
",inquiry(1,l[xx],r[xx]));
			}
			else if (qwe==0)
			{
				int xx,yy;
				scanf("%d%d",&xx,&yy);
				int delta=yy-data[xx];
				data[xx]=yy;
				update(1,l[xx],r[xx],delta);
			}
		}

	}
	
	return 0;
}