stavo risolvendo questo problema problema
Tuttavia mi sembra che i testcase siano sbagliati oppure molto deboli.
Spiegazione problema:
Viene chiesto il costo per costruire un grafo connesso dove sono presenti nodi sicuri e insicuri, per ogni nodo A e B nel grafo deve esistere un path da A a B che non passi per nessun nodo insicuro (A e B possono essere nodi insicuri).
ecco due codici in python che ho trovato online che passano tutti i testcase.
Codice 1:
import sys; input = sys.stdin.readline
class UFDS:
def __init__(self, N):
self.p = [*range(N)]
self.rank = [0]*N
self.n = N
def find_set(self, i):
if self.p[i] == i: return i
self.p[i] = self.find_set(self.p[i])
return self.p[i]
def union(self, i, j):
if (x:=self.find_set(i)) != (y:=self.find_set(j)):
self.n -= 1
if self.rank[x] > self.rank[y]: self.p[y] = x
else: self.p[x] = y; self.rank[y] += self.rank[x] == self.rank[y]
n, m, p = map(int, input().split())
if n == 1: print(0), exit(0)
safe = [1]*n; el = []; lo = [float('inf')]*n
for c in [*map(int, input().split())]: safe[c-1] = 0
if n == 2: print('impossible' if m == 0 else [*map(int, input().split())][2]), exit(0)
for _ in range(m):
a, b, w = map(int, input().split()); a -= 1; b -= 1
if safe[a] and safe[b]: el.append((w, a, b))
elif not safe[a] and not safe[b]: continue
elif safe[a]: lo[b] = min(lo[b], w)
else: lo[a] = min(lo[a], w)
el.sort(); u = UFDS(n); tc = 0
for w, a, b in el:
if u.find_set(a) == u.find_set(b): continue
u.union(a, b); tc += w
if u.n != n-sum(safe)+1: print('impossible'), exit(0)
for i in range(n):
if not safe[i]: tc += lo[i]
print(tc if tc < 1e18 else 'impossible')
codice 2:
from sys import stdin
import sys
import heapq
safeEdges = []
unsafeEdges = []
totalCost = 0
def find(x):
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def merge(x, y):
x = find(x)
y = find(y)
if x == y:
return False
else:
parent[x] = y
return True
numBuildings, numEdges, numUnsafe = tuple(map(int, input().split()))
parent = [i for i in range(0, numBuildings)]
isUnsafe = [False for i in range(0, numBuildings)]
if numEdges < numBuildings - 1:
if numBuildings == 1:
print(0)
else:
print('impossible')
sys.exit()
if numUnsafe > 0:
unsafe = map(int, input().split())
for item in unsafe:
isUnsafe[item - 1] = True
for i in range(0, numEdges):
left, right, cost =tuple(map(int, input().split()))
left = left - 1
right = right- 1
if isUnsafe[left] ^ isUnsafe[right]:
heapq.heappush(unsafeEdges, (cost, left, right))
elif ((not isUnsafe[left]) and (not isUnsafe[right])) or (numBuildings == numUnsafe):
heapq.heappush(safeEdges, (cost, left, right))
while len(safeEdges) > 0:
cost, left, right = heapq.heappop(safeEdges)
if merge(left, right):
totalCost += cost
firstSafe = -1
for i in range(0, numBuildings):
if not isUnsafe[i]:
firstSafe = i
if firstSafe != -1:
for i in range(0, numBuildings):
if (not isUnsafe[i]) and find(firstSafe) != find(i):
print('impossible')
sys.exit()
while len(unsafeEdges) > 0:
cost, left, right = heapq.heappop(unsafeEdges)
if merge(left, right):
totalCost += cost
for i in range (0, numBuildings):
if find(0) != find(i):
print('impossible')
break
elif i == numBuildings - 1:
print(totalCost)
Entrambi i codici non funzionano correttamente nei casi in cui tutti i nodi sono unsafe, esempio:
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
un complete graph dove tutti i nodi sono unsafe, l’opzione corretta sarebbe prendere tutti gli edge, ma il primo codice dice che costruire il grafo è impossibile mentre il secondo da 3 (il risultato corretto è 7).
Quello che ho fatto io è costruire uno spanning tree con i nodi safe, e poi aggiungo uno ad uno i nodi unsafe a questa component, quando tutti i nodi sono unsafe l’unico modo per costruire il grafo è quando è complete, in quel caso il costo è la somma di tutti gli edge.
Il mio codice in c++ è:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef long long ll;
constexpr ll mod = 1000000007;
void print(){cout<<endl;} template <typename T, typename... Types> void print(T var1, Types... var2) {cout<<var1<<" ";print(var2...);}
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("snakes.in", "r", stdin);
#endif
// freopen("snakes.out", "w", stdout);
cout << fixed << setprecision(15);
int t=1;
// cin>>t;
rep(i,t){
solve();
}
}
vi parent,siz;
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void make_set(int v) {
parent[v] = v;
siz[v] = 1;
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] < siz[b])
swap(a, b);
parent[b] = a;
siz[a] += siz[b];
}
}
void solve(){
int n,m,p;
cin>>n>>m>>p;
vi catt(n);
rep(i,p){
int a;
cin>>a;
a--;
catt[a]=1;
}
priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pqb;
priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pqc;
array<ll,3> bad;
int tot = 0;
rep(i,m){
array<ll,3> ed;
cin>>ed[1]>>ed[2]>>ed[0];
ed[1]--;ed[2]--;
tot+=ed[0];
if(!catt[ed[1]] && !catt[ed[2]])pqb.push(ed);
else if(!(catt[ed[1]] && catt[ed[2]]))pqc.push(ed);
else if(n==2) bad = ed;
}
ll cost = 0;
siz.resize(n);
parent.resize(n);
rep(i,n)make_set(i);
while(!pqb.empty()){
array<ll,3> cur = pqb.top();
pqb.pop();
if(find_set(cur[1]) == find_set(cur[2]))continue;
union_sets(cur[1],cur[2]);
cost+=cur[0];
}
while(!pqc.empty()){
array<ll,3> cur = pqc.top();
pqc.pop();
if(find_set(cur[1]) == find_set(cur[2]))continue;
union_sets(cur[1],cur[2]);
cost+=cur[0];
}
bool ok = true;
int ind = find_set(0);
for(int i = 1 ;i < n ;i++)if(find_set(i)!= ind)ok=false;
if(ok){
print(cost);
return;
}
if(p == n && m==n*(n-1)/2){
print(tot);
return;
}
print("impossible");
}