2527: THE END IS COMING!!!
瞎了眼没看清样例，我怕不是个傻叉。。。。
转自题解，然后自己码了码代码
思路还是挺巧妙的，首先我们需要知道这k个名额只能用于不能到达的，日狗这点真的坑
第二，我们还要知道元素可以拆分，分成每一个元素分开计算
第三，我们还要知道怎么建图
我们只有 5 种元素，所以可以全部分开考虑
每种元素单独考虑
每个点拆成两部分，一个用于接受元素，一个用于往外送元素。
源点向每个点的接受元素部分建立流量为当前节点需要元素数量，费用为 1 的边。
向用于外送元素的部分建立流量为当前节点需要元素数量，费用为 0 的边。
外送元素部分向所有能及时赶到的部分建立流量为正无穷，费用为 0 的边，意味着同一个元
素又去了其他地方。
每个接受元素的部分向超级汇点建立流量为当前节点需要元素数量，费用为 0 的边，意味着
这个点接收到了足够多的元素。
每个离起点距离不支持的点记录数量，超过 k 就是无解。
处理过程中跳过这些点就好了
总结一下就是
对于每一个点从源点到这个点建立容量为需求，费用为1的边，从这个点到终点建立容量为需求，费用为0的边
对于可能发生的转移，我们需要一个虚拟节点，代表的是i这个节点能向其它转移的元素的个数，所以从源点开始向虚拟节点连接容量为需求，费用为0的点，同时向所有能转移的点连接容量为需求，费用为0的节点
这样子为什么是正确的呢？
我想了想，对于每一个节点，可以从源点直接拿元素，也可以由其他转移过来，但是最大流是固定的，就是所有的需求，所以即使求最小费用的过程，当你不能从其它节点得到流量，只能通过自己从源点拿元素，费用为1，以保证最大流
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define For(i,a,b) for(int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int prime = 999983;
const int INF = 1e8;
const LL INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
struct Edge{
int from,to,cap,flow,cost;
};
const int maxn = 5000+100;
struct MCMF{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
void init(int n){
this->n = n;
for(int i = 0;i < n; ++i) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap,int cost){
edges.push_back((Edge){from,to,cap,0,cost});
edges.push_back((Edge){to,from,0,0,-cost});
int m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int s,int t,int &flow,int &cost){
for(int i = 0;i < n; ++i) d[i] = INF;
memset(inq,0,sizeof(inq));
d[s] = 0,inq[s] = 1;p[s] = 0,a[s] = INF;
queue<int> Q;
Q.push(s);
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = 0;
for(int i = 0;i < G[u].size(); ++i){
Edge& e = edges[G[u][i]];
if(e.cap > e.flow &&d[e.to] > d[u]+e.cost){
d[e.to] = d[u]+e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u],e.cap-e.flow);
if(!inq[e.to]) {
Q.push(e.to); inq[e.to] = 1;
}
}
}
}
if(d[t] == INF) return false;
flow += a[t];
cost += d[t]*a[t];
int u = t;
while(u != s){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
int Mincost(int s,int t,int &flow,int &cost){
flow = 0,cost = 0;
while(BellmanFord(s,t,flow,cost));
return cost;
}
};
MCMF mcmf;
// const int maxn = 100+10;
int x[maxn],y[maxn],st[maxn],ut[maxn],c[maxn][6];
int sx,sy;
bool keda[maxn];
int main(void)
{
int n,m,k;
cin>>n>>m>>k;
cin>>sx>>sy;
int cnt = 0;
for(int i = 1;i < n; ++i){
cin>>x[i]>>y[i]>>st[i]>>ut[i];
for(int j = 1;j <= m; ++j)
cin>>c[i][j];
int dis =abs(x[i]-sx)+abs(y[i]-sy);
if(dis > st[i])
cnt++;
else
keda[i] = true;
}
if(cnt > k)
return 0*puts("THE END IS COMING!!!!!");
// cout<<cnt<<endl;
int ans = 0;
for(int j = 1;j <= m; ++j){
mcmf.init(2*n+1);
for(int i = 1;i < n; ++i){
if(!keda[i]) continue;
mcmf.AddEdge(0,i,c[i][j],1);
mcmf.AddEdge(i,n+i,c[i][j],0);
mcmf.AddEdge(0,n+i,c[i][j],0);
for(int k = 1;k < n; ++k){
int dis =abs(x[i]-x[k])+abs(y[i]-y[k]);
if(keda[k]&&k != i&&st[i]+ut[i]+dis <= st[k])
{
mcmf.AddEdge(n+i,k,c[i][j],0);
// cout<<i<<" "<<k<<endl;
}
}
mcmf.AddEdge(i,2*n,c[i][j],0);
}
int flow,cost;
ans += mcmf.Mincost(0,2*n,flow,cost);
// ans += cost;
}
cout<<ans<<endl;
// int n,m,s,t;
// scanf("%d %d %d %d",&n,&m,&s,&t);
// int u,v,w,c;
// mcmf.init(n+1);
// while(m--){
// scanf("%d %d %d %d",&u,&v,&w,&c);
// mcmf.AddEdge(u,v,w,c);
// }
// int flow,cost;
// flow = 0,cost = 0;
// mcmf.Mincost(s,t,flow,cost);
// printf("%d %d\n",flow,cost);
return 0;
}
京公网安备 11010502036488号