dfs | Security Badges

Description You are in charge of the security for a large building, with n rooms and m doors between the rooms. The rooms and doors are conveniently numbered from 1 to n, and from 1 to m, respectively.

Door i opens from room ai to room bi , but not the other way around. Additionally, each door has a security code that can be represented as a range of numbers [ci , di ].

There are k employees working in the building, each carrying a security badge with a unique, integer-valued badge ID between 1 and k. An employee is cleared to go through door i only when the badge ID x satisfies ci ≤ x ≤ di .

Your boss wants a quick check of the security of the building. Given s and t, how many employees can go from room s to room t?

Input The first line of input contains three space-separated integers n, m, and k (2 ≤ n ≤ 1,000; 1 ≤ m ≤ 5,000; 1 ≤ k ≤ 109 ). The second line of input contains two space-separated integers s and t (1 ≤ s, t ≤ n; s 6= t). Each of the next m lines contains four space-separated integers ai , bi , ci , and di (1 ≤ ai , bi ≤ n; 1 ≤ ci ≤ di ≤ k; ai 6= bi), describing door i. For any given pair of rooms a, b there will be at most one door from a to b (but there may be both a door from a to b and a door from b to a).

Output Print, on a single line, the number of employees who can reach room t starting from room s.

题意共有n间房间，m扇门，k位员工（编号为1~k）。每扇门连接两个房间，可以允许通过该门的员工编号范围称作code，用闭区间[ci,di]表示。求从房间s出发，最终共有多少人员可以到达房间t。

思路 dfs求出所有起点为s终点为t的路径，对于每一条路径，求出所有code的交集；对于所有路径，求出所有答案的并集。两种效率低下的朴素思路分别为：1.依次对每位员工判断是否能到达终点 2.对每条路径判断有哪些员工可以到达终点。针对第一种思路进行优化，可以将所有员工分为若干区间，同区间内的员工具有共同的性质，即能够一起通过某条路径到达终点，或一起被卡在某条路径的半途。

  1 #include <iostream>

  2 #include <stdio.h>

  3 #include <stdlib.h>

  4 #include <memory.h>

  5 #include <algorithm>

  6

  7 using namespace std;

  8

  9 //邻接表模板

 10 typedef struct adjnode

 11 {

 12     int end;

 13     int c;

 14     int d;

 15     struct adjnode *next;

 16 } Node;

 17 typedef struct adjlist

 18 {

 19     Node *head;

 20 } List;

 21 typedef struct _Graph

 22 {

 23     int vertices;

 24     int edges;

 25     List *array;

 26 }Graph;

 27

 28 Graph* Create(int v)

 29 {

 30     Graph *graph=new Graph;

 31

 32     graph->vertices=v;

 33     graph->edges=0;

 34

 35     graph->array=new List[v+1]; //0~v

 36

 37     for(int i=0;i<=v;i++){

 38         graph->array[i].head=NULL;

 39     }

 40

 41     return graph;

 42 }

 43

 44 void AddEdge(Graph *graph,int begin,int end,int ci,int di)

 45 {

 46     Node *newnode=new Node;

 47

 48     newnode->end=end;

 49     newnode->next=graph->array[begin].head;

 50     newnode->c=ci;

 51     newnode->d=di;

 52     graph->array[begin].head=newnode;

 53

 54     graph->edges++;

 55 }

 56

 57

 58 int t,ans=0;

 59 int edges[10005];

 60

 61 bool dfs(Graph *g,int cur,int l,int r,bool vis[1005]){

 62     vis[cur]=true;

 63

 64     if(cur==t){

 65         return true;

 66     }

 67

 68     Node *p=g->array[cur].head;

 69     while(p){

 70         if(!vis[p->end] && p->c<=l && p->d>=r){

 71             if(dfs(g,p->end,l,r,vis))

 72                 return true;

 73         }

 74         p=p->next;

 75     }

 76

 77     return false;

 78 }

 79

 80 int main()

 81 {

 82     int n,m,k,s;

 83     cin>>n>>m>>k>>s>>t;

 84

 85     Graph *hotel=Create(n);

 86

 87     int a,b,u,v;

 88     for(int i=0;i<m;i++){

 89         cin>>a>>b>>u>>v;

 90

 91         AddEdge(hotel,a,b,u,v);

 92         edges[i*2]=u;

 93         edges[i*2+1]=v+1;  //[a,b]∪[b+1,c]等同于[a,c]

 94     }

 95

 96     sort(edges,edges+2*m);

 97     int cnt=unique(edges,edges+2*m)-edges;

 98

 99     bool vis[1005];

100

101     for(int i=1;i<cnt;i++){

102         memset(vis,false,sizeof(vis));

103         if(dfs(hotel,s,edges[i-1],edges[i]-1,vis))  //规定受检区间左闭右开

104             ans+=(edges[i]-edges[i-1]);

105     }

106

107     cout<<ans<<endl;

108

109     return 0;

110 }

来源 2017-2018 acm-icpc northwest regional contest

参考 https://blog.csdn.net/yz467796454/article/details/78753171 ；官方题解

巴特西

dfs | Security Badges

最新文章

热门文章