POJ 1716 Integer Intervals差分制約

 1 #include <stdio.h>

 2 #include <string.h>

 3 #include <vector>

 4 #include <queue>

 5 

 6 const int INF = 0x3f3f3f3f;

 7 

 8 struct Edge

 9 {

10     int v, w;

11     Edge(){};

12     Edge(int v, int w)

13     {

14         this->v = v;

15         this->w = w;

16     }

17 };

18 

19 std::vector<Edge>map[10010];

20 int dist[10010];

21 bool inque[10010];

22 

23 void spfa(int s)

24 {

25     std::queue<int>q;

26     memset(inque, 0, sizeof(inque));

27     dist[s] = 0;

28     q.push(s);

29     inque[s] = 1;

30     while(!q.empty())

31     {

32         int u = q.front();

33         q.pop();

34         inque[u] = 0;

35         for(int i = 0; i < map[u].size(); i++)

36         {

37             int v = map[u][i].v;

38             if(dist[v] < dist[u] + map[u][i].w)

39             {

40                 dist[v] = dist[u] + map[u][i].w;

41                 if(!inque[v])

42                 {

43                     q.push(v);

44                     inque[v] = 1;

45                 }

46             }

47         }

48     }

49 }

50 

51 int main()

52 {

53     int n;

54     int x, y;

55     while(scanf("%d", &n) != EOF)

56     {

57         for(int i = 0; i <= 10001; i++)

58         {

59             map[i].clear();

60         }

61         int low = INF, high = 0;

62         for(int i = 0; i < n; i++)

63         {

64             scanf("%d %d", &x, &y);

65             map[x].push_back(Edge(y+1, 2));

66             if(low > x)low = x;

67             if(high < y)high = y;

68         }

69         for(int i = low; i <= high+1; i++)

70         {

71             map[0].push_back(Edge(i, 0));

72             map[i].push_back(Edge(i+1, 0));

73             map[i+1].push_back(Edge(i, -1));

74             dist[i] = -INF;

75         }

76         map[0].push_back(Edge(high+1, 0));

77         spfa(low);

78         printf("%d
", dist[high+1] - dist[low]);

79     }

80     return 0;

81 }