2021.12.19 eleveni的刷题记录

别人100pts：

#include

3.4 网络流

3.4.1 费用流

https://www.luogu.com.cn/problem/P2469

#include
#include
#include
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N=160010;
const int inf=0x3f3f3f3f;
int n,m,start,endi,cnt=1,head[N];
int maxnflow,maxncost,vis[N],flow[N],pre[N],dis[N];
struct node{
	int to,next,val,cost;
}a[N*3];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline void addi(int u,int v,int w,int x){
	++cnt;
	a[cnt].to=v;
	a[cnt].val=w;
	a[cnt].cost=x;
	a[cnt].next=head[u];
	head[u]=cnt;
}
inline void add(int u,int v,int w,int x){
	addi(u,v,w,x);addi(v,u,0,-x);
}
inline int spfa(int s,int t){
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	queueq;
	dis[s]=0;flow[s]=inf;vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=a[i].next){
			int v=a[i].to;
			if(dis[v]>dis[x]+a[i].cost&&a[i].val){
				dis[v]=dis[x]+a[i].cost;
				flow[v]=min(flow[x],a[i].val);
				pre[v]=i;
				if(!vis[x])vis[v]=1,q.push(v);
			}
		}
	}
	return dis[t]!=inf;
}
inline void update(int s,int t){
	int x=t;
	while(x!=s){
		int xi=pre[x];
		a[xi].val-=flow[t];
		a[xi^1].val+=flow[t];
		x=a[xi^1].to;
	}
	maxnflow+=flow[t];
	maxncost+=flow[t]*dis[t];
}
inline void EK(int s,int t){
	while(spfa(s,t))update(s,t);
}

int main(){
	n=read();m=read();
	start=n*2+1,endi=n*2+2;
	for(int i=1;i<=n;i++){
		int x=read();
		add(start,i,1,0);
		add(start,i+n,1,x);
		add(i+n,endi,1,0);
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		u=read();v=read();w=read();
		if(u>v)swap(u,v);
		add(u,v+n,1,w);
	}
	EK(start,endi);
	cout<

#include
#include
#include
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define int long long
const int N=20;
int n,m,K,mod;
struct Matrix{
	int num[N][N];
	Matrix(){
		memset(num,0,sizeof(num));
	}
	inline Matrix operator *(const Matrix &b)const{
		Matrix c;
		for(int i=1;i<=K;i++)
		for(int j=1;j<=K;j++)
		for(int k=1;k<=K;k++)
		c.num[i][j]=(c.num[i][j]+num[i][k]*b.num[k][j]%mod)%mod;
		return c;
	}
}ans,basic;

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline Matrix operator ^(Matrix x,int y){
	Matrix fin=x;--y;
	while(y){
		if(y&1)fin=fin*x;
		x=x*x;
		y>>=1;
	}
	return fin;
}

signed main(){
	K=read();
	for(int i=1;i<=K;i++)ans.num[i][1]=read();
	for(int i=K;i>=1;i--){
		if(i0)ans=(basic^(m-K))*ans;
	//cout<<"ans "<

#include
#include
#include
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define int long long
const int N=20;
int n,m,K,mod,sum[N];
struct Matrix{
	int num[N][N];
	Matrix(){
		memset(num,0,sizeof(num));
	}
	inline Matrix operator *(const Matrix &b)const{
		Matrix c;
		for(int i=1;i<=K+1;i++)
		for(int j=1;j<=K+1;j++)
		for(int k=1;k<=K+1;k++)
		c.num[i][j]=(c.num[i][j]+num[i][k]*b.num[k][j]%mod)%mod;
		return c;
	}
}ans,basic;

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline Matrix operator ^(Matrix x,int y){
    Matrix fin;
    if(y==0)return fin;
	fin=x;--y;
	while(y>0){
		if(y&1)fin=fin*x;
		x=x*x;
		y>>=1;
	}
	return fin;
}

signed main(){
	K=read();
	for(int i=1;i<=K;i++)ans.num[i][1]=read();
	for(int i=K;i>=1;i--){
		if(i

#include
#include
#include
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N=210;
const int inf=0x3f3f3f3f;
int n,f[N][N*N],sum[N];
struct node{
	int wait,eat;
	bool operator <(const node &b)const{
		return eat>b.eat;
	}
}a[N];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i].wait=read(),a[i].eat=read();
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].wait;
	memset(f,inf,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	for(int j=0;j<=sum[i];j++){
		if(j>=a[i].wait)f[i][j]=min(f[i][j],max(f[i-1][j-a[i].wait],j+a[i].eat));
		f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].eat));
	}
	int ans=inf;
	for(int i=0;i<=sum[n];i++)ans=min(ans,f[n][i]);
	cout<