省选模拟13
T1
费用流，拆点，把点按奇偶分类
偶数的直接拆成 \(\frac{a_i}{2}\) ，奇数的也一样，然后枚举哪一边的流量多，再给他加上就行
Code
#include
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,ans=inf,p,U,S,T;
int a[60],c[60][60],trans[60];
int L[60],R[60];
namespace FLOW{
int COST;
int dis[1010],q[1010],h,t;
int head[1010],ver[6000],to[6000],edge[6000],cost[6000],tot=1;
bool inq[1010],vis[1010];
inline void add(int x,int y,int z,int w){
ver[++tot]=y;edge[tot]=z;cost[tot]= w;to[tot]=head[x];head[x]=tot;
ver[++tot]=x;edge[tot]=0;cost[tot]=-w;to[tot]=head[y];head[y]=tot;
}
inline bool spfa(){
for(int i=1;i<=T;i++) dis[i]=inf,inq[i]=0;
dis[S]=0,q[h=t=1]=S,inq[S]=1;memset(vis,0,sizeof(vis));
while(h<=t){
int x=q[h++];inq[x]=0;
for(int i=head[x];i;i=to[i]) if(edge[i]){
int y=ver[i];
if(dis[y]>dis[x]+cost[i]){
dis[y]=dis[x]+cost[i];
if(!inq[y]) q[++t]=y,inq[y]=1;
}
}
}
return dis[T]!=inf;
}
int dfs(int x,int in){
if(x==T) return in;
int res=in,go;vis[x]=1;
for(int i=head[x];i;i=to[i]) if(edge[i]){
int y=ver[i];
if(vis[y]) continue;
if(dis[y]==dis[x]+cost[i]){
go=dfs(y,min(res,edge[i]));
res-=go,edge[i]-=go,edge[i^1]+=go;
COST+=go*cost[i];
}
if(!res) break;
}
return in-res;
}
inline void clear(){for(int i=1;i<=T;i++) head[i]=0;tot=1;COST=0;}
inline int MinCost(){while(spfa()) dfs(S,inf);return COST;}
}using FLOW::add;
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
n=read();S=n*2+1,T=n*2+2;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=read();
for(int i=1;i<=n;i++) if(a[i]&1) trans[++p]=i;if(p&1) puts("-1"),exit(0);
U=(1<>(i-1)&1) L[trans[i]]++;else R[trans[i]]++;
FLOW::clear();
for(int i=1;i<=n;i++) add(S,i,L[i],0),add(i+n,T,R[i],0);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(i,j+n,inf,c[i][j]);
ans=min(ans,FLOW::MinCost());
}
printf("%lld\n",ans);
return 0;
}
T2
对于每个节点都维护一些线段，只用记录他的左右端点
合并的时候考虑哪一条线段作为第一条线段，再用状压 \(dp\) 出以这个线段为左端点时的最小的右端点
注意把劣的去掉，同时在状压的过程中记录合并的顺序
Code
#include
#define int long long
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n;
struct seg{
int l,r,id;
inline bool operator<(const seg &b)const{return (l==b.l)?rmp;
vectorg[100010],ans[100010];
vectorvec[100010],tmp;
int f[100010],ff[100010],son[100010],id[100010];
void dfs1(int x){
if(!g[x].size()) return ;int p=0;
for(auto y:g[x]) dfs1(y),son[y]=++p;
if(g[x].size()==1) return swap(vec[x],vec[g[x][0]]),void();
int U=(1<<(g[x].size()-1))-1;
mp.clear();tmp.clear();seg t;
for(int i=0;i>(j-1))&1)){
ed=vec[id[j]].size();
pos=lower_bound(vec[id[j]].begin(),vec[id[j]].end(),t)-vec[id[j]].begin();
if(pos!=ed&&vec[id[j]][pos].r T3
考虑 \(O(n^2)\) 的暴力，对每个点都把他能直接传染到的点和他连边
然后再用 \(tarjan\) 缩点，最后剩下几个没有入度的点，答案就是几
考虑用点分治来优化这个过程
对于每个分治中心，把所有的路径长度都找出来
对每个长度都分别建立虚点，由长向短依次连边
再看每个点，由长度大于等于他的第一个虚点连边，再由他向他能传染到的跨过分治中心的最远的点连边
这里只考虑跨过分治中心的，没有跨过的会在其他地方考虑到
最后再用 \(tarjan\) 缩点，找到没有入度的点就行
Code
#include
#define int long long
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,ans,deg[4300010],r[300010],N;
rint head[300010],ver[600010],to[600010],tot;
int edge[600010];
rint dfn[4300010],low[4300010],clo,mn[4300010];
rint scc[4300010],col,stk[4300010],p;
int S,rt,mxdis;
rint siz[4300010],mx[4300010],id[4300010];
bool vis[4300010];
vectorg[4100000],gg[3420000];
vectorvec;
queueq;
inline void add(rint x,rint y,rint z){ver[++tot]=y;edge[tot]=z;to[tot]=head[x];head[x]=tot;}
void tarjan(int x){
dfn[x]=low[x]=++clo;vis[x]=1;stk[++p]=x;
for(auto y:g[x]){
if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
rint k;col++;mn[col]=N+1;
do{k=stk[p--];scc[k]=col;vis[k]=0;mn[col]=min(mn[col],k);}while(k!=x);
}
}
void getrt(int x,int fa){
siz[x]=1,mx[x]=0;
for(rint i=head[x];i;i=to[i]){
int y=ver[i];
if(y==fa||vis[y]) continue;
getrt(y,x);siz[x]+=siz[y];mx[x]=max(mx[x],siz[y]);
}
mx[x]=max(mx[x],(rint)S-siz[x]);
if(mx[x]=0){
pos=upper_bound(vec.begin(),vec.end(),range)-vec.begin();
if(pos) g[x].emplace_back(id[pos-1]);
}
for(rint i=head[x];i;i=to[i]){
int y=ver[i];
if(y==fa||vis[y]) continue;
dfs2(y,x,dis+edge[i]);
}
}
inline void calc(int x){
vec.clear();mxdis=-1;getdis(x,0,0);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(rint i=0;i