2020.8.7合宿

奇妙な道
description小宇は歴史の本から古い文明を知った.この文明は各方面で高度に発達しており、交通面でも例外ではない.考古学者はすでに知っていて、この文明は全盛期にnの都市があって、番号は1⋯n1cdots n 1⋯nです.m m m m本の道路はこれらの都市の間に接続され、各道路は2つの都市を接続し、両地の住民が便利に行き来できるようにしている.1対の都市の間には複数の道路が存在する可能性がある.史料によると、この文明的な交通ネットワークは2つの奇妙な特徴を満たしている.まず、この文明はデジタルKを崇拝するので、どの道に対しても、それが接続されている2つの都市をそれぞれu u uとv v v vとすると、必ず1≦u−v≦K 1leq|u−v|leq K 1≦u−v≦Kを満たす.また、どの都市もちょうど偶数の道路につながっている(0も偶数とされている).しかし、時間が長すぎるため、具体的な交通ネットワークはもう知ることができません.小宇はこのn n n都市の間にどれだけの可能性のある接続方法があるのか知りたくて、彼女はあなたに助けを求めました.メソッド数は大きいかもしれませんが、メソッド数モード100000007 1000000007 1000000007の結果を出力するだけです.
solution
dpを考慮して,i i i番目のi i個の点をf[i][j][k][S]f[i][j][k][S]f[i][j][k][S]で表し,j j j個の辺を用いて,i i iはすでに1⋯i−k 1cdots i−k 1⋯i−kの辺を結んでおり,前k個の点の読書のパリティはS S S S S S S
i−k+1 i−k+1 i−k+1 i−k+1という点では,1つのエッジ,すなわち
f [ i ] [ j + 1 ] [ k ] [ S ′ ] + = f [ i ] [ j ] [ k ] [ S ] f[i][j+1][k][S^\prime]+=f[i][j][k][S] f[i][j+1][k][S′]+=f[i][j][k][S]
つながっていなくてもいい
f [ i ] [ j ] [ k − 1 ] [ S ′ ] + = f [ i ] [ j ] [ k ] [ S ] f[i][j][k-1][S^\prime]+=f[i][j][k][S] f[i][j][k−1][S′]+=f[i][j][k][S]
また、距離S S Sがk k kである点の度数が偶数の場合、i+1 i+1 i+1に移行する
code

#include 
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=35;
const int inf=2e9;
const int mod=1e9+7;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,m,K;
int f[N][N][N][1<<9];

int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	read(n),read(m),read(K);
	f[1][0][0][0]=1;
	int ss=(1<<K+1)-1;
	Rep(i,1,n){
		Rep(j,0,m)
			Rep(S,0,ss)
				_Rep(k,min(i-1,K),1){
					if(j<m)f[i][j+1][k][S^(1<<k)^1]+=f[i][j][k][S],f[i][j+1][k][S^(1<<k)^1]%=mod;
					f[i][j][k-1][S]+=f[i][j][k][S],f[i][j][k-1][S]%=mod;
				}
		Rep(j,0,m)if(i<n)
			Rep(S,0,ss)
				if(!(S&(1<<K))){
					f[i+1][j][i>=K?K:i][(S<<1)&ss]+=f[i][j][0][S];
					f[i+1][j][i>=K?K:i][(S<<1)&ss]%=mod;
				}
	}
	printf("%d
",f[n][m][0][0]);
	return 0;
}

運搬工
description
小涵は小宇に小さなゲームを推薦した.ゲームはこんな感じで、n× n n\times n n×nの地図には,いくつかの格子に障害物がある.運搬業者を雇って、これらの障害物を全部取り除く必要があります.しかし、操作するたびに、運搬業者に1行または1列の障害物をすべて除去させるしかありません.運搬業者にi行目の障害物を取り除くにはa i aが必要です.i ai元;運搬業者にj列目の障害物を除去させるには、b j b_を払う必要があります.j bj元.小涵は小宇に、できるだけ少ない回数でこれらの障害物を除去しなければならないと言った.複数の案があれば、できるだけ少ない費用を払わなければならない.結局、宇さんは長い間第一関門を突破したことがないと思っていたので、助けを求めるしかなかった.
n ≤ 100 , a i , b i ≤ 100 n\leq 100,a_i,b_i\leq 100 n≤100,ai​,bi​≤100
solution
最初の質問は裸の二分図マッチングです
2番目の質問で「最小限の回数を前提に」が要求されなければ、費用によって最小割を走ることになります.
だからこの問題のやり方はそれらを結びつけることです
セットΔ = 1 0 6\Delta=10^6 Δ=106,s s s方向i i i i連a i+Δ a_i+\Delta ai​+Δの辺、i+ni+ni+n方向t t連b i+Δ b_i+\Delta bi​+Δの辺、中間はinfを建てます
走り出した最大ストリーム/Δ\Delta Δ最初の質問です最大フロー%Δ\Delta Δ2番目の質問です

#include 
using namespace std;
#define int long long
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=1e5+5;
const int inf=2e12;
const int Q=1e6+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,s,t;
int a[N],b[N];
int head[N],cnt;
int dep[N];
int ans;
char str[205][205];

struct Edge{
	int to,next,w;	
}e[N*20];

void add(int x,int y,int c){
	e[++cnt]=(Edge){y,head[x],c},head[x]=cnt;
	e[++cnt]=(Edge){x,head[y],0},head[y]=cnt;	
}

bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		RepG(i,u){
			int v=e[i].to;
			if(e[i].w&&!dep[v]){
				dep[v]=dep[u]+1;
				q.push(v);
				if(v==t)return true;
			}
		}
	}
	return false;
}

int dfs(int u,int flow){
	if(u==t)return flow;
	int rest=flow,k;
	for(int i=head[u];~i&&rest;i=e[i].next){
		int v=e[i].to;
		if(e[i].w&&dep[v]==dep[u]+1){
			k=dfs(v,min(rest,e[i].w));	
			if(!k)dep[v]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			rest-=k;
		}
	}
	return flow-rest;
}

void dinic(){
	ans=0;
	int tmp;
	while(bfs())
		while(tmp=dfs(s,inf))ans+=tmp;	
}

signed main()
{
	freopen("worker.in","r",stdin);
	freopen("worker.out","w",stdout);
	memset(head,-1,sizeof(head)),cnt=1;
	scanf("%d",&n);
	s=0,t=2*n+1;
	Rep(i,1,n)scanf("%s",str[i]+1);
	Rep(i,1,n)
		Rep(j,1,n)
			if(str[i][j]=='*')add(i,j+n,inf);
	Rep(i,1,n)read(a[i]);
	Rep(i,1,n)read(b[i]);
	Rep(i,1,n)add(s,i,a[i]+Q);
	Rep(i,1,n)add(i+n,t,b[i]+Q);
	dinic();
	printf("%lld
",ans/Q);
	printf("%lld
",ans%Q);
	return 0;
}
/*
3
...
.*.
**.
10 5 17
1 8 4

*/