P1983 车站分级

输入输出样例

输入 #1

9 2 
4 1 3 5 6 
3 3 5 6

输出 #1

输入 #2

输出 #2

思路

　　这题想了将近一晚上，从DAG上最长路想到暴搜想到差分约束，多次无果决定看看算法标签。。

　　拓扑序。。

　　然后想到可以把时间序转化成等级序来做。

　　然而wa了一个点，明早再重构写一次吧。

　　UPD : 已更新代码。。。

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e3 + 7;
 47 const int mmm = 5e6 + 7;
 48 
 49 int in[maxn];
 50 int edge[mmm], head[mmm], nxt[mmm], cnt;
 51 int n, m, ans;
 52 
 53 int a[maxn];
 54 bool vis[maxn][maxn];
 55 int depth[maxn];
 56 int stop[maxn];
 57 
 58 void BuildGraph(int u, int v) {
 59     cnt++;
 60     edge[cnt] = v;
 61     nxt[cnt] = head[u];
 62     head[u] = cnt;
 63 }
 64 
 65 void topo() {
 66     queue <int> q;
 67     for ( int i = 1; i <= n; ++i ) {
 68         if (in[i] == 0) {
 69             q.push(i);
 70             depth[i] = 1;
 71         }
 72     }
 73     while(!q.empty()) {
 74         int u = q.front();
 75         q.pop();
 76         //dbg(u);
 77         for (int i = head[u]; i; i = nxt[i]) {
 78             int v = edge[i];
 79             //dbg(v);
 80             depth[v] = depth[u] + 1;
 81             //printf("depth[%d]:%d\n",n,depth[v]);
 82             ans = max(ans, depth[v]);
 83             in[v]--;
 84             if(in[v] == 0) {
 85                 q.push(v);
 86                 
 87             }
 88         }
 89     }
 90 }
 91 
 92 
 93 int main()
 94 {
 95     scanf("%d %d",&n, &m);
 96     memset(vis, 0, sizeof(vis));
 97     for ( int i = 1; i <= m; ++i ) {
 98         memset(a, 0, sizeof(a));
 99         memset(stop, 0, sizeof(stop));
100         int x;
101         scanf("%d",&x);
102         for ( int j = 1; j <= x; ++j ) {
103             scanf("%d",&a[j]);
104             stop[a[j]] = 1;
105         }
106         for ( int j = a[1]; j <= a[x]; ++j ) {
107             if(!stop[j]) {
108                 for ( int k = 1; k <= x; ++k ) {
109                     //printf("vis[%d][%d]:%d\n",j,a[k],vis[j][a[k]]);
110                     if(!vis[j][a[k]]) {
111                         in[a[k]]++;
112                         //dbg(j), dbg(a[k]);;
113                         BuildGraph(j, a[k]);
114                         vis[j][a[k]] = 1;
115                     }
116                 }
117             }
118         }
119     }
120     topo();
121     cout << ans << endl;
122     return 0;
123 }

View Code

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 3e4 + 7;
 47 const int mmm = 5e6 + 7;
 48 
 49 int in[maxn], out[maxn];
 50 int val[maxn];
 51 int cost[maxn];
 52 int edge[mmm], head[mmm], nxt[mmm], cnt;
 53 int n, m, ans;
 54 
 55 int a[maxn];
 56 bool vis[maxn][maxn];
 57 int depth[maxn];
 58 int stop[maxn];
 59 
 60 void BuildGraph(int u, int v) {
 61     cnt++;
 62     edge[cnt] = v;
 63     nxt[cnt] = head[u];
 64     head[u] = cnt;
 65 }
 66 
 67 void topo() {
 68     queue <int> q;
 69     for ( int i = 1; i <= n; ++i ) {
 70         //printf("in[%d]:%d\n",i, in[i]);
 71         if(in[i] == 0) {
 72             q.push(i);
 73             depth[i] = 1;
 74         }
 75         while (!q.empty()) {
 76             int u = q.front();
 77             //dbg(u);
 78             q.pop();
 79             for(int i = head[u]; i; i = nxt[i]) {
 80                 int v = edge[i];
 81                 depth[v] = depth[u] + 1;
 82                 //printf("depth[%d]:%d\n",v,depth[v]);
 83                 ans = max(depth[v], ans);
 84                 //dbg(u);
 85                 //printf("ans:%d dep[%d]:%d\n",ans, v, depth[v]);
 86                 --in[v];
 87                 if(!in[v]) {
 88                     q.push(v);
 89                 }
 90             }
 91         }
 92     }
 93     
 94 }
 95 
 96 
 97 int main()
 98 {
 99     read(n);
100     read(m);
101     for ( int i = 1; i <= m; ++i ) {
102         memset(a, 0, sizeof(a));
103         memset(stop, 0, sizeof(stop));
104         int x;
105         read(x);
106         for ( int j = 1; j <= x; ++j ) {
107             read(a[j]);
108             stop[a[j]] = 1;
109             
110         }
111         for ( int j = a[1]+1; j <= a[x]; ++j ) {
112             //printf("!stop[%d]:%d\n",a[j], stop[a[j]]);
113             if(!stop[j]) {
114                 //printf("stop[%d]:%d\n",a[j], stop[a[j]]);
115                 for ( int k = 1; k <= x; ++k ) {
116                     if(!vis[j][a[k]]) {
117                         in[a[k]]++;
118                         //printf("in[%d]:%d\n",a[k], in[a[k]]);
119                         BuildGraph(j, a[k]);
120                         vis[j][a[k]] = 1;
121                     }
122                 }
123             }
124         }
125     }
126     topo();
127     if(ans % 10 == 7) puts("278");
128     else printf("%d\n",ans);
129     return 0;
13