题解：CF325C Monsters and Diamonds
vanueber
·
·
题解
先考虑最小值怎样求得。
建图连边，对每个怪物建点 1\sim n，对于每个限制建立虚点，虚点向原怪物连边，边权是爆出的钻石数量，新怪物往虚点连边，边权是这个怪物的个数。
开始是先从只能爆出钻石的怪物开始，如果不存在只能爆出钻石的怪物，说明每个点至少有一条边连向其他点。这样形成了一个内向基环树森林，怪永远打不完。
然后从这些点开始跑 dijkstra 算法，但这不是朴素的，因为边权代表的东西都不同，但这样依然是对的。
我们证明：对于怪物，我们最终得到的是他的最小值，对于虚点，我们得到的是该策略下怪物贡献和的最小值。
::::info[简证]{open}
沿用 dijkstra 算法的证明：即证当点从堆中取出时，得到了最小值。
如果取出的是怪物，由于它的相邻节点是虚点，连边是普通边权，正确性同 dijkstra 算法。
如果取出的是虚点，代表它所对应的怪物贡献和都取到了最小值，不重不漏。
::::
这样跑下来就得到了最小值，$d_u = +\infin$ 说明这个点的答案是 `-1 -1`，因为有答案的点一定会被虚点松弛。
接下来考虑最大值，在做最小值的过程中，有些点 $d_u = +\infin$，这些点被标记为禁止使用，如果一个怪物的策略里有禁止使用的点，他的答案是 $-2$。
然后拓扑排序，虚点的值为 $\sum w\times s_v$，怪物则是 $\max s_v + w$。原图上有环，但拓扑排序会规避这个问题，最终 $ans=-2$ 的点一定成环了，他的入度不为 $0$。
最终答案记得取 $\min$。
```cpp
#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f3f3f3f3f;
inline int read(){
int w=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<1)+(w<<3)+(ch^48);
ch=getchar();
}
return w*f;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int N=2e5+10;
int n,m,idx;
int dis[N],vis[N],used[N],tar[N];
int ans[N][2],xu[N];
struct rule{
int id;
int cnt;
umap<int,int> mp;
}R[N];
struct node{
int v,w;
bool operator <(const node &b)const{
return w>b.w;
}
};
vector<node> G[N],g[N];
void dijkstra(){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
priority_queue<node> Q;
rep(i,1,m){
if(R[i].mp.empty()){
dis[R[i].id]=min(dis[R[i].id],R[i].cnt);
Q.push({R[i].id,dis[R[i].id]});
}
}
while(!Q.empty()){
int u=Q.top().v;
Q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto [v,w]:G[u]){
if(v>n){
if(dis[v]==INF) dis[v]=0;
dis[v]+=w*dis[u];
used[v]+=w;
if(used[v]==tar[v]){
Q.push({v,dis[v]});
}
}
else{
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
Q.push({v,dis[v]});
}
}
}
}
rep(i,1,n) ans[i][0]=(dis[i]==INF)?-1:dis[i];
}
bool forbid[N];
int maxd[N],ind[N],inq[N];
void topo_sort(){
memset(maxd,-0x3f,sizeof maxd);
rep(i,1,n){
if(ans[i][0]==-1) forbid[i]=1;
}
queue<int> Q;
rep(i,1,m){
auto [id,cnt,mp]=R[i];
if(forbid[id]) continue;
bool flag=1;
for(auto [v,w]:mp){
if(forbid[v]){
flag=0;break;
}
}
if(!flag) continue;
g[xu[i]].push_back({id,cnt});
++ind[id];
for(auto [v,w]:mp){
if(forbid[v]) continue;
g[v].push_back({xu[i],w});
++ind[xu[i]];
}
}
rep(i,1,m){
auto [id,cnt,mp]=R[i];
if(forbid[id]) continue;
if(ind[id]==0){
if(!inq[id]) inq[id]=1,Q.push(id);
maxd[id]=max(maxd[id],cnt);
}
if(ind[xu[i]]==0) Q.push(xu[i]),maxd[xu[i]]=0;
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(auto [v,w]:g[u]){
if(v<=n) maxd[v]=max(maxd[v],maxd[u]+w);
else{
if(maxd[v]<0) maxd[v]=0;
maxd[v]+=maxd[u]*w;
}
--ind[v];
if(!ind[v]) Q.push(v);
}
}
rep(i,1,n){
if(ans[i][0]==-1) ans[i][1]=-1;
else ans[i][1]=(maxd[i]<0||ind[i]!=0)?-2:maxd[i];
}
}
signed main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
cin>>m>>n;
idx=n;
rep(i,1,m){
int x=read(),c=read(),cnt=0;
umap<int,int> mp;
rep(j,1,c){
int val=read();
if(val==-1) ++cnt;
else ++mp[val];
}
xu[i]=++idx;
G[idx].push_back({x,cnt});
for(auto [u,w]:mp){
tar[idx]+=w;
G[u].push_back({idx,w});
}
R[i]=(rule){x,cnt,mp};
}
dijkstra();
topo_sort();
rep(i,1,n){
if(ans[i][0]!=-1&&ans[i][0]!=-2) ans[i][0]=min(ans[i][0],314000000ll);
if(ans[i][1]!=-1&&ans[i][1]!=-2) ans[i][1]=min(ans[i][1],314000000ll);
}
rep(i,1,n){
cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
}
#ifndef ONLINE_JUDGE
fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
```