专栏文章

题解：CF325C Monsters and Diamonds

vvanueber
CF325C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindbqx8
此快照首次捕获于
2025/12/02 00:33
3 个月前
此快照最后确认于
2025/12/02 00:33
3 个月前
查看原文
先考虑最小值怎样求得。
建图连边，对每个怪物建点 1∼n1\sim n，对于每个限制建立虚点，虚点向原怪物连边，边权是爆出的钻石数量，新怪物往虚点连边，边权是这个怪物的个数。
开始是先从只能爆出钻石的怪物开始，如果不存在只能爆出钻石的怪物，说明每个点至少有一条边连向其他点。这样形成了一个内向基环树森林，怪永远打不完。
然后从这些点开始跑 dijkstra 算法，但这不是朴素的，因为边权代表的东西都不同，但这样依然是对的。
dud_u 代表只有一只 uu 时爆出的最小钻石数。算法流程：从 uu 开始松弛节点，如果 vv 时虚点，那么 dv←dv+w×dud_v \gets d_v + w\times d_u，否则 dv←min⁡(dv,du+w)d_v \gets \min(d_v,d_u+w) 。
我们证明：对于怪物，我们最终得到的是他的最小值，对于虚点，我们得到的是该策略下怪物贡献和的最小值。
简证
沿用 dijkstra 算法的证明：即证当点从堆中取出时，得到了最小值。
如果取出的是怪物，由于它的相邻节点是虚点，连边是普通边权，正确性同 dijkstra 算法。
如果取出的是虚点，代表它所对应的怪物贡献和都取到了最小值，不重不漏。
这样跑下来就得到了最小值，du=+∞d_u = +\infin 说明这个点的答案是 -1 -1，因为有答案的点一定会被虚点松弛。
接下来考虑最大值，在做最小值的过程中，有些点 du=+∞d_u = +\infin，这些点被标记为禁止使用，如果一个怪物的策略里有禁止使用的点，他的答案是 −2-2。
然后拓扑排序，虚点的值为 ∑w×sv\sum w\times s_v，怪物则是 max⁡sv+w\max s_v + w。原图上有环，但拓扑排序会规避这个问题，最终 ans=−2ans=-2 的点一定成环了，他的入度不为 00。
最终答案记得取 min⁡\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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...