两道网络流，一道dp
CF 1423B
比较裸的网络流，我们二分这个最短工期，每次用最大流跑一次二分图匹配就好了
struct Dinic
{
struct Edge
{
int from,to,cap,flow;
Edge(int f,int t,int c,int w):from(f),to(t),cap(c),flow(w){}
};
int n,m,s,t;//size of point and line and the start point and end point
vector<int>d,cur;
vector<bool>vis;
vector<Edge>E;
vector<vector<int>>G;
const int INF=0x3f3f3f3f;
Dinic(int n,int m):n(n),m(m)
{
d.resize(n+1);
vis.resize(n+1,false);
G.resize(n+1);
cur.resize(n+1);
}
void add_edge(int from,int to,int cap)
{
E.push_back({from,to,cap,0});
G[from].push_back(E.size()-1);
E.push_back({to,from,0,0});
G[to].push_back(E.size()-1);
}
bool bfs()//get the depth of every point
{
fill(vis.begin(),vis.end(),false);
queue<int>q;
q.push(s);
d[s]=0;
vis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();++i)
{
auto& e=E[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
ll dfs(int x,int a)
{
if(x==t||a==0)return a;
ll res=0,f;
for(int& i=cur[x];i<G[x].size();++i)
{
auto& e=E[G[x][i]];
if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
E[G[x][i]^1].flow-=f;
res+=f;
a-=f;
if(a<=0)break;
}
}
return res;
}
ll maxflow(int s,int t)
{
this->s=s;
this->t=t;
ll ans=0;
while(bfs())
{
fill(cur.begin(),cur.end(),0);
ans+=dfs(s,INF);//INF is the now flow
}
return ans;
}
};
struct Road{
int u,v,d;
};
void solve(){
int n,m;
cin>>n>>m;//total 2*n+2;
vector<Road>E(m+1);
int l=INT_MAX,r=INT_MIN;
for(int i=1;i<=m;++i){
cin>>E[i].u>>E[i].v>>E[i].d;
l=min(l,E[i].d);
r=max(r,E[i].d);
}
int source=2*n+1,sink=2*n+2;
function<bool(int)>check=[&](int cur_time){
Dinic dinic(2*n+3,0);
for(int i=1;i<=n;++i){
dinic.add_edge(source,i,1);
dinic.add_edge(n+i,sink,1);
}
for(int i=1;i<=m;++i){
if(E[i].d<=cur_time){
dinic.add_edge(E[i].u,E[i].v+n,1);
}
}
ll maxflow=dinic.maxflow(source,sink);
return maxflow==n;
};
ll ans=-1;
while(l<=r){
int m=(l+r)>>1;
if(check(m)){
ans=m;
r=m-1;
}else{
l=m+1;
}
}
cout<<ans<<'\n';
return;
}
CF 884F
最小费用流裸题，我们对每个S，向cnt[i]连一条容量为cnt[i]的边，然后因为是对称的位置，所以另起n/2个点，相互连线，最后n/2个点向汇点连线，之后跑最小费用流就好了
struct MCMF{
struct edge{
int u,v;
ll cap,cost;
};
const ll INF=1e18;
int s,t;//source and des
ll mincostflow;//the MCMF answer
ll maxflow;//the maxflow
vector<edge>Edge;//all edges
vector<vector<int>>E;//the graph
vector<ll>dis;//distance between source and i
vector<int>vis;//whether this point in the loose queue or not
MCMF(int n,int source,int sink){
E.resize(n+1);
dis.resize(n+1);
vis.resize(n+1);
s=source;
t=sink;
mincostflow=0;
maxflow=0;
}
void add_edge(int u,int v,int cap,int cost){
E[u].push_back(Edge.size());
Edge.push_back({u,v,cap,cost});
E[v].push_back(Edge.size());
Edge.push_back({v,u,0,-cost});
}
bool spfa(){
fill(dis.begin(),dis.end(),INF);
queue<int>q;
q.push(s);
vis[s]=1;
dis[s]=0;
while(!q.empty()){
auto tmp=q.front();
q.pop();
vis[tmp]=0;
for(int id:E[tmp]){
auto e=Edge[id];
int to=e.v;
if(e.cap>0&&dis[to]>dis[tmp]+e.cost){
dis[to]=dis[tmp]+e.cost;
if(!vis[to]){
q.push(to);
vis[to]=1;
}
}
}
}
return dis[t]!=INF;
}
ll dfs(int u,ll flow){
if(u==t)
return flow;
vis[u]=1;
ll ans=0;
for(int i=E[u].size()-1;i>=0;--i){
int id=E[u][i];
auto e=Edge[id];
int v=e.v;
if(e.cap&&!vis[v]&&dis[v]==dis[u]+e.cost){
ll cur_flow=dfs(v,min(flow-ans,e.cap));//the flow of the remaining graph
if(cur_flow){
if(ans+cur_flow>flow)
break;
mincostflow+=cur_flow*e.cost;
ans+=cur_flow;
Edge[id^1].cap+=cur_flow;
Edge[id].cap-=cur_flow;
}
}
}
vis[u]=0;
return ans;
}
ll get_mcmf(){
maxflow=0;
while(spfa()){
int cur_flow;
while((cur_flow=dfs(s,INF)))maxflow+=cur_flow;
}
return mincostflow;
}
};
void solve(){
int n;
cin>>n;
string s;
cin>>s;
s=')'+s;
vector<int>b(n+1);
vector<int>cnt(26);
ll sum=0;
for(int i=1;i<=n;++i){
cin>>b[i];
sum+=b[i];
cnt[s[i]-'a']++;
}
int source=n/2+26+1,sink=source+1;
MCMF mf(n/2+26+3,source,sink);
for(int i=0;i<26;++i){
mf.add_edge(source,i+1,cnt[i],0);
for(int j=1;j<=n/2;++j){
int val=0;
if(s[j]-'a'==i){
val=max(val,b[j]);
}
if(s[n-j+1]-'a'==i){
val=max(val,b[n-j+1]);
}
mf.add_edge(i+1,26+j,1,-val);
}
}
for(int i=1;i<=n/2;++i){
mf.add_edge(26+i,sink,2,0);
}
mf.get_mcmf();
cout<<-mf.mincostflow<<'\n';
return;
}
CF 497E
${dp[i][j]}$表示当前在i，用了j步，用前缀和和滚动数组优化一下就可以了
void solve(){
int n,a,b,k;
cin>>n>>a>>b>>k;
vector<int>dp(n+1),sum(n+1);
if(a>b){// you could only move in one side of b(up or down)
n-=b;
a-=b;
}else{
n=b-1;
a=b-a;
}
dp[a]=1;
for(int i=a;i<=n;++i)sum[i]=1;
for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
dp[j]=((sum[n]-sum[j>>1])-dp[j]+2*MOD)%MOD;
}
for(int j=1;j<=n;++j){
sum[j]=(sum[j-1]+dp[j])%MOD;
}
}
cout<<sum[n]<<'\n';
return;
}