ABC 214 G,H 题解
G
考虑建一张图。
途中\(p_i,q_i\)之间有一条边。
则问题转化成，在每条边上写上两两不同的数字，使得每一条边写的数字和两端的数字不同。
考虑容斥。
钦定一些边，然后给边定向，使得每一个点的出度\(\leq 1\)。
可以发现构成的连通块是个环，直接破环为链dp。
然后对于所有环做一次卷积就是答案。
时间复杂度\(O(N^2\log N)\)。
code:
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MOD=1e9+7;
const int MAXN=3003;
int fact[MAXN];
int n,fa[MAXN],siz[MAXN];
int root(int x){
return fa[x]=(fa[x]==x? x:root(fa[x]));
}
void merge(int u,int v){
if(root(u)==root(v)) return ;
siz[root(v)]+=siz[root(u)];
fa[root(u)]=root(v);
}
int dp[2][2][MAXN][MAXN];
void add(int & A,int B){
A+=B;
if(A>=MOD) A-=MOD;
}
vector<int> calc(int len){
if(len==1) return {1,1};
rep(f,2) rb(i,1,len) memset(dp[0][f][i],0,sizeof(dp[0][f][i])),memset(dp[1][f][i],0,sizeof(dp[1][f][i]));
dp[0][1][2][1]=1;
dp[1][0][2][1]=1;
dp[0][0][2][0]=1;
vector<int> Ret(len+1,0);
rb(i,2,len){
rep(j,2)
rep(f,2){
rep(k,i)
if(dp[j][f][i][k]){
int val=dp[j][f][i][k];
if(i==len){
add(Ret[k],val);
if(!j) add(Ret[k+1],val);
if(!f) add(Ret[k+1],val);
}
else{
add(dp[j][0][i+1][k],val);
if(!f) add(dp[j][0][i+1][k+1],val);
add(dp[j][1][i+1][k+1],val);
}
}
}
}
return Ret;
}
vector<int> mul(vector<int> A,vector<int> B){
vector<int> ret(A.size()+B.size()-1,0);
rep(i,A.size()) rep(j,B.size()) add(ret[i+j],1ll*A[i]*B[j]%MOD);
return ret;
}
int q[MAXN],p[MAXN];
int main(){
fact[0]=1;
rb(i,1,3000) fact[i]=1ll*fact[i-1]*i%MOD;
scanf("%d",&n);
rb(i,1,n) scanf("%d",&p[i]);
rb(i,1,n) scanf("%d",&q[i]);
rb(i,1,n) fa[i]=i,siz[i]=1;
rb(i,1,n) merge(q[i],p[i]);
vector<vector<int> > poly;
rb(i,1,n) if(root(i)==i) poly.PB(calc(siz[i]));
priority_queue<mp,vector<mp>,greater<mp> > heap;
rep(i,poly.size()) heap.push(II(poly[i].size(),i));
while(heap.size()>=2){
int i,j;
i=heap.top().SEC;
heap.pop();
j=heap.top().SEC;
heap.pop();
poly[i]=mul(poly[j],poly[i]);
heap.push(II(poly[i].size(),i));
}
int i=heap.top().SEC;
int ans=0;
rep(j,poly[i].size()){
if(j&1)
add(ans,MOD-1ll*fact[n-j]%MOD*poly[i][j]%MOD);
else
add(ans,1ll*fact[n-j]%MOD*poly[i][j]%MOD);
}
cout<<ans<<endl;
return 0;
}
H
很显然是费用流。
但是spfa会被卡。
需要用dijkstra费用流。
方法：令\(h[i]\)表示当前从\(s\)到\(i\)的最短路减去上一次增广前\(s\)到\(i\)的最短路。
然后考虑对\(h\)跑对短路。
边权\(u\rightarrow v,w\)变成\(w+dis[u]-dis[v]\)。可以发现这个总是\(\geq 0\)。
然后就做完了。
code:
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<‘0‘||ch>‘9‘){
// ch=getchar();
// }
// while(ch>=‘0‘&&ch<=‘9‘){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
#define int LL
typedef pair<LL,LL> mp;
/*}
*/
const int GRAPH_SIZE= 4e5+10;
int s=0,t=GRAPH_SIZE-1;
struct EDGE{
int u,v,c,cos;
};
vector<EDGE> e;
vector<int> each[GRAPH_SIZE];
int maxflow,mincost;
int flow[GRAPH_SIZE];
int dis[GRAPH_SIZE],las[GRAPH_SIZE],h[GRAPH_SIZE];
bool fi=0;
int cnt=0;
bool spfa(){
flow[s]=1e17;
if(!fi){
fi=1;
fill(dis,dis+GRAPH_SIZE,1e17);
dis[s]=0;
rb(now,0,cnt*2){
if(dis[now]==1e17) continue;
// cerr<<now<<‘ ‘<<dis[now]<<endl;
for(auto it:each[now]){
int to,f,c;
to=e[it].v;
f=e[it].c;
c=e[it].cos;
if(f<=0) continue;
assert(to>now);
if(dis[to]>dis[now]+c){
dis[to]=dis[now]+c;
las[to]=it;
flow[to]=min(flow[now],f);
}
}
}
}
else{
fill(h,h+GRAPH_SIZE,1e17);
h[s]=0;
priority_queue<mp,vector<mp>,greater<mp> > heap;
heap.push(II(0,s));
while(!heap.empty()){
mp Now=heap.top();
heap.pop();
if(Now.FIR!=h[Now.SEC]) continue;
int now=Now.SEC;
for(auto it:each[now]){
int to,f,c;
to=e[it].v;
f=e[it].c;
c=e[it].cos+dis[now]-dis[to];
if(f<=0) continue;
if(h[to]>h[now]+c){
h[to]=h[now]+c;
las[to]=it;
flow[to]=min(flow[now],f);
heap.push(II(h[to],to));
}
}
}
rep(i,GRAPH_SIZE) dis[i]=min((LL)(1e17),dis[i]+h[i]);
}
// cerr<<dis[t]<<endl;
return dis[t]<=1e16;
}
void KM(){
while(spfa()){
maxflow+=flow[t];
mincost+=dis[t]*flow[t];
// cout<<mincost<<" "<<maxflow<<endl;
int now=t;
while(now!=s){
e[las[now]].c-=flow[t];
e[las[now]^1].c+=flow[t];
now=e[las[now]].u;
}
}
}
void make_edge(int U,int V,int C,int COS){
EDGE tmp;
tmp.u=U;
tmp.v=V;
tmp.c=C;
tmp.cos=COS;
e.PB(tmp);
each[U].PB(e.size()-1);
swap(tmp.u,tmp.v);
tmp.c=0;
tmp.cos=-COS;
e.PB(tmp);
each[V].PB(e.size()-1);
}
const int MAXN=2e5+10;
int n,m,k;
int in[MAXN],out[MAXN];
int belong[MAXN];
vector<int> g[MAXN],rg[MAXN];
int u[MAXN],v[MAXN];
stack<int> sta;
bool vis[MAXN];
map<mp,bool> app;
int x[MAXN];
void dfs(int now){
vis[now]=1;
for(auto it:g[now]) if(!vis[it]) dfs(it);
sta.push(now);
}
void rdfs(int now){
belong[now]=cnt;
for(auto it:rg[now]) if(!belong[it]) rdfs(it);
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
rb(i,1,m){
scanf("%lld%lld",&u[i],&v[i]);
g[u[i]].PB(v[i]);
rg[v[i]].PB(u[i]);
}
// cout<<g[1].size()<<endl;
rb(i,1,n)
if(!vis[i]) dfs(i);
while(!sta.empty()){
int now=sta.top();
sta.pop();
if(!belong[now]){
++cnt;
rdfs(now);
}
}
// cout<<"!"<<cnt<<endl;
rb(i,1,n){
LL xx;
scanf("%lld",&xx),x[belong[i]]+=xx;
}
rb(i,1,cnt) in[i]=i*2-1,out[i]=i*2;
make_edge(s,in[belong[1]],k,0);
rb(i,1,m){
int U,V;
U=belong[u[i]];
V=belong[v[i]];
if(U==0||V==0) continue;
if(U!=V&&!app[II(U,V)]){
app[II(U,V)]=1;
assert(U<V);
// cout<<out[U]<<" "<<in[V]<<endl;
assert(out[U]<in[V]);
make_edge(out[U],in[V],k,0);
}
}
// cout<<cnt<<endl;
rb(i,1,cnt) make_edge(in[i],out[i],1,-x[i]),make_edge(in[i],out[i],k,0);
rb(i,1,cnt) make_edge(out[i],t,k,0);
KM();
cout<<-mincost<<endl;
return 0;
}