-
讨论 (0)
这个用户还没有发布过讨论 -
贡献 (0)
啊哦,这个用户还没贡献过题目和题解~ -
递交 (2)
最近递交
状态 题目 递交者 时间 内存 语言 递交时间 P1409 纪念品分组 sky1231 676ms 3.508 MiB Python 3 2021-07-02 10:29:45 P1409 纪念品分组 sky1231 0ms 0 Bytes C++ 2021-07-02 10:29:30 P1409 纪念品分组 sky1231 684ms 3.512 MiB Python 3 2021-07-02 09:55:44 P1389 婚礼上的小杉 sky1231 44ms 2.402 MiB C++ 2021-03-19 18:19:46 P1257 水王争霸 sky1231 9ms 476.0 KiB C++ 2021-03-19 17:43:20 P1389 婚礼上的小杉 sky1231 26ms 512.0 KiB C++ 2021-03-19 17:39:14 P1380 盗窃-巴黎阳光普照 sky1231 4ms 256.0 KiB C++ 2021-03-19 16:53:40 P1380 盗窃-巴黎阳光普照 sky1231 4ms 256.0 KiB C++ 2021-03-19 16:48:12 P1380 盗窃-巴黎阳光普照 sky1231 4ms 256.0 KiB C++ 2021-03-19 16:45:51 P1380 盗窃-巴黎阳光普照 sky1231 4ms 256.0 KiB C++ 2021-03-19 16:42:17
个人简介
這個人真的很懶,個人簡介是網絡流模板:
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;
namespace dts
{
typedef long long ll;
double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
struct network_flows
{
vector<ll> e;
vector<ll> pre;
vector<ll> vis;
vector<vector<ll> > cw;
vector<vector<ll> > ce;
vector<double> f;
vector<double> u;
vector<vector<double> > c;
vector<vector<double> > p;
deque<ll> q;
void clear_flow()
{
e.clear();
pre.clear();
vis.clear();
f.clear();
u.clear();
}
void clear_edge()
{
clear_flow();
cw.clear();
ce.clear();
c.clear();
p.clear();
}
ll size()
{
return cw.size();
}
void set_size(ll size_v)
{
clear_edge();
cw.resize(size_v);
ce.resize(size());
c.resize(size());
p.resize(size());
}
void add_edge(ll x,ll y,double c_v,double p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}
void prepare(ll s,ll t)
{
clear_flow();
f.resize(size(),0);
f[s]=oo_max;
e.resize(size(),-1);
u.resize(size(),oo_max);
u[s]=0;
pre.resize(size(),-1);
pre[s]=s;
vis.resize(size(),0);
}
ll bfs(ll s,ll t,double &flow,double &cost)
{
prepare(s,t);
for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
{
ll now=q.front();
for (ll i=0;i<cw[now].size();i++)
if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
flow=f[t];
cost=u[t];
return (pre[t]!=-1);
}
void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
{
double temp_flow,temp_cost;
while (bfs(s,t,temp_flow,temp_cost))
{
for (ll i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
flow+=temp_flow;
if (typ==0)
cost+=temp_cost;
else if (typ==1)
cost+=(temp_flow*temp_cost);
}
}
};
};
int main()
{
dts::main();
}