CF 277E
费用流题目，我们把每个点拆分成in和out,原点向in连一条容量为2，费用为0的边，代表每个点最多有两个儿子
再向in和out分别连线，容量为1，cost为dis，代表对应的费用
最后从out向汇点连线，容量为1，费用为0，代表每个节点最多一个儿子(1不连线)
struct MCMF{
struct edge{
int u,v;
int cap;
double cost;
};
const double INF=1e12;
int s,t;//source and des
double mincostflow;//the MCMF answer
ll maxflow;//the maxflow
vector<edge>Edge;//all edges
vector<vector<int>>E;//the graph
vector<double>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,double 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;
}
double dfs(int u,double flow){
if(u==t)
return flow;
vis[u]=1;
double 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){
double cur_flow=dfs(v,min(flow-ans,(double)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()){
double cur_flow;
while((cur_flow=dfs(s,INF)))maxflow+=cur_flow;
}
return mincostflow;
}
};
struct node{
double x,y;
};
void solve(){
int n;
cin>>n;
vector<node>a(n+1);
for(int i=1;i<=n;++i){
cin>>a[i].x>>a[i].y;
}
sort(a.begin()+1,a.end(),[&](node aa,node bb){
return aa.y>bb.y;
});
if(a[1].y==a[2].y){
cout<<-1<<'\n';
return;
}
int S=0,T=2*n+1;
MCMF mf(2*n+1,S,T);
function<double(int,int)>dis=[&](int i,int j){
double x_dis=a[i].x-a[j].x;
double y_dis=a[i].y-a[j].y;
return sqrt(x_dis*x_dis+y_dis*y_dis);
};
for(int i=1;i<=n;++i){
mf.add_edge(S,i,2,0);//limit that for every node, it could only have two offspring
if(i>=2)mf.add_edge(i+n,T,1,0);
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(a[i].y<=a[j].y)continue;
double d=dis(i,j);
mf.add_edge(i,j+n,1,d);//cap is 1 indicates that it could only have one parent
}
}
mf.get_mcmf();
if(mf.maxflow!=n-1){
cout<<-1<<'\n';
return;
}
cout.precision(10);
cout<<mf.mincostflow<<'\n';
return;
}
CF 1139E
把club和能力值抽象为点，然后分别连线，由于我们直接的O(VE)来说复杂度不过，所以我们倒着来，每次从当前的mex来往前搜
void solve(){
int n,m;
cin>>n>>m;
vector<int>p(n+1),c(n+1);
vector<vector<int>>E(5000+1);
for(int i=1;i<=n;++i)cin>>p[i];
for(int i=1;i<=n;++i)cin>>c[i];
int d;cin>>d;
vector<int>ans(d+1);
int res=0;
vector<int>invalid(n+1);
vector<int>leave(d+1);
for(int i=1;i<=d;++i){
cin>>leave[i];
invalid[leave[i]]=1;
}
for(int i=1;i<=n;++i){
if(!invalid[i]){
E[p[i]].push_back(c[i]);
}
}
int cur_ans=0;
vector<int>vis(n+1),match(m+1,-1);
function<bool(int)>dfs=[&](int x){
for(int v:E[x]){
if(vis[v]==cur_ans){
continue;
}
vis[v]=cur_ans;
if(match[v]==-1||dfs(match[v])){
match[v]=x;
return true;
}
}
return false;
};
for(int i=d;i>=1;--i){
for(int j=res;;++j){
++cur_ans;
if(!dfs(j)){
res=j;
break;
}
}
ans[i]=res;
E[p[leave[i]]].push_back(c[leave[i]]);
}
for(int i=1;i<=d;++i){
cout<<ans[i]<<"\n";
}
return;
}