标签：Real Around Estate int back add val push 805
- 网络流的【世界线】模型：在每个时间点，新建三个点分别表示某个助手在该时间点的状态，向下一时间点的对应点连一条流量无穷的边以刻画时间流逝
- 难以求出出售房产的顺序，既然如此，我们就要求当前房产只有在能被出售的前提下才给到某个助手
- 但是我们必须要把某个房产给到一个助手呀？没关系，给小绿，用决策包容性解决这个问题
- 用铅笔画图，在允许擦改的同时避免了黑笔的漏墨问题
- 本题费用流的最大流前提保证了每个房产都会被处理
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int opt[205],val[205];
vector<int>a[805],c[805],d[805],e[805];
int s,t,n,ans,dis[805],l[805],pr1[805],pr2[805];
bool v[805];
void add(int u,int v,int l,int w)
{
a[u].push_back(v);
a[v].push_back(u);
c[u].push_back(l);
c[v].push_back(0);
d[u].push_back(a[v].size()-1);
d[v].push_back(a[u].size()-1);
e[u].push_back(w);
e[v].push_back(-w);
}
int q[805*805];
bool spfa()
{
for(int i=0;i<=4*n+1;i++)
{
dis[i]=INT_MAX;
v[i]=false;
}
int L=0,R=1;
q[1]=s;
dis[s]=0;
l[s]=INT_MAX;
v[s]=true;
while(L<R)
{
L++;
int n1=q[L];
v[n1]=false;
for(int i=0;i<a[n1].size();i++)
{
if(c[n1][i]>0&&dis[n1]+e[n1][i]<dis[a[n1][i]])
{
l[a[n1][i]]=min(l[n1],c[n1][i]);
dis[a[n1][i]]=dis[n1]+e[n1][i];
pr1[a[n1][i]]=n1;
pr2[a[n1][i]]=i;
if(v[a[n1][i]]==false)
{
R++;
q[R]=a[n1][i];
v[a[n1][i]]=true;
}
}
}
}
return dis[t]!=INT_MAX;
}
void update()
{
int p=t;
while(p!=s)
{
c[pr1[p]][pr2[p]]-=l[t];
c[p][d[pr1[p]][pr2[p]]]+=l[t];
ans=ans-l[t]*e[pr1[p]][pr2[p]];
p=pr1[p];
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
s=0;
t=4*n+1;
for(int i=0;i<=4*n+1;i++)
{
a[i].clear();
c[i].clear();
d[i].clear();
e[i].clear();
}
ans=0;
for(int i=1;i<=n;i++)
{
cin>>opt[i];
if(opt[i]==1)
{
cin>>val[i];
ans+=val[i];
add(s,i,1,0);
add(i,i+n,1,1);
add(i,i+2*n,1,val[i]/10+((val[i]%10)>0));
add(i,i+3*n,1,0);
add(i,t,1,val[i]);
}
else
{
add(i+n,t,1,0);
add(i+2*n,t,1,0);
add(i+3*n,t,1,0);
}
}
for(int i=1;i<n;i++)
{
add(i+n,i+n+1,n,0);
add(i+2*n,i+2*n+1,n,0);
add(i+3*n,i+3*n+1,n,0);
}
while(spfa())
{
update();
}
cout<<ans<<endl;
}
return 0;
}
标签：Real,
Around,
Estate,
int,
back,
add,
val,
push,
805
From： https://www.cnblogs.com/watersail/p/18427145