这道题我竟有三种思路!!!
当然有两种事实证明不可行
题目描述:
K(1≤K≤100)只奶牛分散在N(1≤N≤1000)个牧场.现在她们要集中起来进餐.牧场之间有M(1≤M≤10000)条有向路连接,而且不存在起点和终点相同的有向路.她们进餐的地点必须是所有奶牛都可到达的地方.那么,有多少这样的牧场呢?
输入样例:
第一行输入三个整数 k,n,m,意义如题目所描述
接下来有k行,分别表示奶牛所在的牧场编号
接下来有m行,每行2个数,表示x to y 有一条边
这道题的思路主要就是:
建反图,枚举每一个点,将题目转变成图的连通性问题
上代码
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
#define maxn 20010
using namespace std ;
typedef pair<int,int>pa ;
priority_queue<pa,vector<pa>,greater<pa> >q ;
int x , y , z ;
struct dy{
int x , y , z , next ;
}a[maxn];
int head[maxn] , vis[maxn] , dis[maxn] ;
int cow[maxn] ;
int n , m , k , t ;
void add(int x , int y, int z){
a[++t].x = x ;
a[t].y = y ;
a[t].z = z ;
a[t].next = head[x] ;
head[x] = t ;
}int ans ;
void dij(int s){
// memset(dis,0x7f,sizeof(dis)) ;
for(int i = 1 ; i <= n ; i ++)
dis[i] = 0x7fffffff ;
memset(vis,0,sizeof(vis)) ;
dis[s] = 0 ;
q.push(make_pair(dis[s],s)) ;
vis[s] = 0 ;
while(!q.empty()){
int u = q.top().second ;
q.pop() ;
if(vis[u]) continue ;
vis[u] = true ;
for(int i = head[u] ; i ; i = a[i].next){
int v = a[i].y ;
if(dis[v] > dis[u] + a[i].z){
dis[v] = dis[u] + a[i].z ;
ans = max(ans,dis[v]) ;
q.push(make_pair(dis[v],v)) ;
}
}
}
}
int main(){
scanf("%d%d%d",&k,&n,&m) ;
for(int i = 1 ; i <= k ; i ++){
scanf("%d",&x) ;
cow[i] = x ;
}
for(int i = 1 ; i<= m ; i ++){
scanf("%d%d",&x,&y) ;
add(y,x,1) ;
}
int tot = 0 ;int flag = 0 ;
for(int i = 1 ; i <= n ; i ++){
dij(i) ;
for(int i = 1 ; i <= k ; i ++){
if(dis[cow[i]] >= 0x7fffffff)
flag = 1 ;
}
if(!flag){
tot ++ ;
}flag = 0 ;
}
printf("%d",tot) ;
}
以上就是代码
我用的堆优化dij
不过好像比较慢 QAQ