这道题我竟有三种思路!!!

当然有两种事实证明不可行

题目描述:

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