Summer Holiday

　

summer holiday

题目

样例

先求出图的所有连通分量,然后每个分量缩成一点,构成DAG图求入度为零的点(所代表的分量)就是我们需要单独通知的分量.且我们每次都是选择该分量中代价最小的那个点通知即可！

#include <iOStream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define _for1(i,a,b) for( int i=(a); i<(b); ++i)
#define _for2(i,a,b) for( int i=(a); i>(b); i--)
#define _rep1(i,a,b) for( int i=(a); i<=(b); ++i)
#define _rep2(i,a,b) for( int i=(a); i>=(b); i--)
typedef long long ll;
using namespace std;
#define maxn 1005
int n, m;
int pay[maxn],minpay[maxn];//电话费
vector<int> G[2005];
int dfn[maxn], low[maxn],sccno[maxn],ins[maxn];
int scccnt, tclock;
int ind[maxn];
stack<int> s;
void tarjan(int u) {
	dfn[u] = low[u] = ++tclock;
	s.push(u);
	ins[u] = 1;
	int sz = G[u].size();
	_for1(i, 0, sz) {
		int v = G[u][i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (ins[v])
			low[u] = min(low[u], low[v]);
	}
	if (low[u] == dfn[u]) {
		scccnt++;
		minpay[scccnt] = INF;
		int v = 1;
		while (1)
		{
			int v = s.top();
			s.pop();
			sccno[v] = scccnt;
			ins[v] = 0;
			minpay[scccnt] = min(minpay[scccnt], pay[v]);
			if (v == u)
				break;
		}
	}
}

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		mem(dfn, 0);
		mem(low, 0);
		mem(sccno, 0);
		mem(ins, 0);
		mem(ind, 0);
		_rep1(i, 1, n) {
			scanf("%d", &pay[i]);
			G[i].clear();
		}
		while (m--) {
			int x, y;
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
		}
		scccnt = tclock = 0;
		_rep1(i, 1, n)
			if (!dfn[i])
				tarjan(i);
		_rep1(u,1,n)
			_for1(i, 0, G[u].size()) {
			int v = G[u][i];
			int x = sccno[u], y = sccno[v];
			if (x != y)
				ind[y]++;
		}
		int cnt = 0, sum = 0;
		_rep1(i,1,scccnt)
			if (ind[i] == 0) {
				cnt++;
				sum += minpay[i];
			}
		printf("%d %d\n", cnt, sum);
	}
	return 0;
}

文章最后发布于: 2019-07-27 20:42:41

相关阅读

Summer Holiday（强连通入门）（缩点）

                                          Summer Holiday                     Time Limit: