1 条题解
-
1Dry_ice LV 8 MOD @ 2020-08-12 21:17:00
看腻了简单版的 \(A+B\),来个费用流。
struct node
{
int to,dis;
bool operator < (const node &rhs) const
{
return dis>rhs.dis;
}
};
int d[10],preu[10],pree[10];
bool inq[10];
int e=1,w[10],r[10],first[10],next[10],cost=0,flow=0,tail[10],h[10];
void link(int u,int v,int re,int weight)
{
next[++e]=first[u];
first[u]=e;
tail[e]=v;
r[e]=re;
w[e]=weight;
next[++e]=first[v];
first[v]=e;
tail[e]=u;
r[e]=0;
w[e]=-weight;
}
int s=1,t=3;
bool vis[100050];
inline void dijkstra()
{
for (int i=1;i<=5;i++)
{
vis[i]=0;
d[i]=1000000;
}
d[s]=0;
priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.empty();
q.push(pair<int,int>(0,s));
while (!q.empty())
{
pair <int,int> rhs=q.top();
q.pop();
int u=rhs.second;
if (vis[u])
continue;
for (int i=first[u];i;i=next[i])
{
int v=tail[i];
if (r[i]>0 && d[v]>d[u]+w[i]+h[u]-h[v])
{
d[v]=d[u]+w[i]+h[u]-h[v];
preu[v]=u;
pree[v]=i;
q.push(pair<int,int>(d[v],v));
}
}
}
}
inline void MinCostMaxFlow()
{
memset(h,0,sizeof(h));
while (1)
{
dijkstra();
if (d[t]==1000000)
break;
else
{
for (int u=1;u<=3;u++)
h[u]+=d[u];
int delta=1000000;
for (int u=t;u!=s;u=preu[u])
{
int e=pree[u];
delta=min(delta,r[e]);
}
flow+=delta;
cost+=delta*h[t];
for (int u=t;u!=s;u=preu[u])
{
int e=pree[u];
r[e]-=delta;
r[e^1]+=delta;
}
}
}
}
inline void solve()
{
int a=read(),b=read();
link(1,2,1,a);
link(2,3,1,b);
MinCostMaxFlow();
cout << cost << endl;
}
- 1