hdu 3998

统计不相交LIS个数
MAX FLOW
dinic...太慢了，SAP竟然0ms
dp直接n2去做，记录每个元素结尾的LIS长度
建图的时候，dp[i]=1的与源点建图，dp[i]=LIS的与汇点建图，dp[i] == dp[j] + 1, i, j 建图
跑一边最大流
  1 #include <bits/stdc++.h>
  2 
  3 const int INF = 0x3f3f3f3f;
  4 const int MAXN = 1e3+10;
  5 const int MAXM = 1e6+10;
  6 
  7 int a[MAXN];
  8 int dp[MAXN];
  9 int ans[MAXN];
 10 int tot, head[MAXN];
 11 int layer[MAXN];
 12 int cur[MAXN];
 13 int sta[MAXN];
 14 int top;
 15 int gap[MAXN];
 16 int n, m;
 17 
 18 struct Edge {
 19     int u, v, cap, next;
 20     Edge(){}
 21     Edge(int _u, int _v, int _cap, int _next)
 22     {
 23         u = _u;
 24         v = _v;
 25         cap = _cap;
 26         next = _next;
 27     }
 28 } edge[MAXM];
 29 
 30 void init()
 31 {
 32     memset(head, 0, sizeof head);
 33     tot = 1;
 34 }
 35 
 36 void addEdge(int u, int v, int cap)
 37 {
 38     edge[++tot] = Edge(u, v, cap, head[u]);
 39     head[u] = tot;
 40 }
 41 
 42 void bfs(int src,int sink)
 43 {
 44     memset(layer, -1, sizeof(layer));
 45     memset(gap, 0, sizeof(gap));
 46     gap[0] = 1;
 47     int que[MAXN];
 48     int front,rear;
 49     front = rear = 0;
 50     layer[sink] = 0;
 51     que[rear++] = sink;
 52     while(front != rear)
 53     {
 54         int u = que[front++];
 55         if(front == MAXN)
 56             front = 0;
 57         for(int i = head[u]; i > 0; i = edge[i].next)
 58         {
 59             int v = edge[i].v;
 60             if(layer[v] != -1) 
 61                 continue;
 62             que[rear++] = v;
 63             if(rear == MAXN)rear=0;
 64             layer[v] = layer[u]+1;
 65             ++gap[layer[v]];
 66         }
 67     }
 68 }
 69 int SAP(int src,int sink)
 70 {
 71     int res = 0;
 72     top = 0;
 73     bfs(src,sink);
 74     memcpy(cur, head, sizeof(head));
 75     int u = src;
 76     int i;
 77     while(layer[src] < n) {
 78         if(u == sink) {
 79             int temp = INF;
 80             int inser;
 81             for (i = 0; i < top; ++i)
 82                 if (temp > edge[sta[i]].cap) {
 83                     temp = edge[sta[i]].cap;
 84                     inser = i;
 85                 }
 86             for (i = 0; i < top; ++i) {
 87                 edge[sta[i]].cap -= temp;
 88                 edge[sta[i]^1].cap += temp;
 89             }
 90             res += temp;
 91             top = inser;
 92             u = edge[sta[top]].u;
 93         }
 94         if (u != sink && gap[layer[u]-1] == 0)
 95             break;
 96         for (i = cur[u]; i > 0; i = edge[i].next)
 97             if (edge[i].cap > 0 && layer[u] == layer[edge[i].v] + 1)
 98                 break;
 99         if(i > 0) {
100             cur[u] = i;
101             sta[top++] = i;
102             u = edge[i].v;
103         }
104         else {
105             int min = n;
106             for (i = head[u]; i > 0; i = edge[i].next) {
107                 if (edge[i].cap == 0)
108                     continue;
109                 if (min > layer[edge[i].v]) {
110                     min = layer[edge[i].v];
111                     cur[u] = i;
112                 }
113             }
114             --gap[layer[u]];
115             layer[u] = min+1;
116             ++gap[layer[u]];
117             if(u != src)
118                 u = edge[sta[--top]].u;
119         }
120     }
121     return res;
122 }
123 
124 
125 int getLIS()
126 {
127     int len = 0;
128     dp[1] = 1;
129     for (int i = 2; i <= n; ++i) {
130         dp[i] = 1;
131         for (int j = i-1; j >= 1; --j) {
132             if (a[i] > a[j]) {
133                 dp[i] = std::max(dp[i], dp[j] + 1);
134             }
135         }
136         len = std::max(len, dp[i]);
137         //printf("dp[%d] = %d
", i, dp[i]);
138     }
139     //printf("len = %d
", len);
140     return len;
141 }
142 
143 
144 int main()
145 {
146     while (~scanf("%d", &n)) {
147         init();
148         a[0] = -INF;
149         for (int i = 1; i <= n; ++i)
150             scanf("%d", a+i);
151         int len = getLIS();
152 
153         int src = 0, sink = n+1;
154         for (int i = 1; i <= n; ++i) {
155             if (dp[i] == 1) {
156                 addEdge(src, i, 1);
157                 addEdge(i, src, 0);
158             }
159             if (dp[i] == len) {
160                 addEdge(i, sink, 1);
161                 addEdge(sink, i, 0);
162             }
163         }
164 
165         for (int i = 1; i <= n; ++i) {
166             for (int j = i+1; j <= n; ++j) {
167                 if (dp[j] == dp[i] + 1) {
168                     addEdge(i, j, 1);
169                     addEdge(j, i, 0);
170                 }
171             }
172         }
173 
174         // run max_flow
175         int res = SAP(src, sink);
176         printf("%d
%d
", len, res);
177     }
178 }
View Code