二次联通门 : 密码锁
然而是假的联通门。。。
题目描述
hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,…xk为开，其他开关为关时，密码锁才会打开。
他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）
本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有的钱他哪里能逃过被chenzeyu97 NTR的命运？>_< 于是，他为了虐爆czy，也为了去泡更多的妹子，决定打开这把锁。但是他那么神的人根本不屑这种”水题”。于是，他找到了你。
你的任务很简单，求出最少需要多少步才能打开密码锁，或者如果无解的话，请输出-1。
输入
第1行，三个正整数N，K，M，如题目所述。
第2行，K个正整数，表示开关x1,x2,x3..xk必须为开，保证x两两不同。
第三行，M个正整数，表示size[i]，size[]可能有重复元素。
输出
输出答案，无解输出-1。
样例输入
10 8 2 1 2 3 5 6 7 8 9 3 5
样例输出
2
提示
【样例输入2】
3 2 1
1 2
3
【样例输出2】
-1
【数据规模】
对于50%的数据，1≤N≤20，1≤k≤5，1≤m≤3;
对于另外20%的数据，1≤N≤10000，1≤k≤5,1≤m≤30;
对于100%的数据，1≤N≤10000，1≤k≤10，1≤m≤100。
/* 将每个点拆成俩个点x，x’，能匹配的点xy从x向y’ 连边权值为1费用 Dist[i][j]，源点向x连边，x’向汇连边，都是权值1 费用0，然后一遍 最小费用最大流就可以出解 复制的hzwer的思路。。。 90分 */ #include <cstring> #include <cstdio> #include <queue> #define Max 10005 #define INF 1e8 namespace Z { void read (int &now) { now = 0; register char word = getchar (); while (word < '0' || word > '9') word = getchar (); while (word >= '0' && word <= '9') { now = now * 10 + word - '0'; word = getchar (); } } inline int min (const int &_Qos_swc, const int &_Cos_ses) { return _Qos_swc < _Cos_ses ? _Qos_swc : _Cos_ses; } } int S, T = 45; int M, N, K; int key[Max]; int size[Max]; int Answer; int Count; int date[Max]; int number[Max]; int cost[Max / 100][Max / 100]; bool visit[Max]; int dis[Max]; void Bfs (int res) { memset (visit, false, sizeof (visit)); std :: queue <int> Queue; visit[res] = true; dis[res] = 0; Queue.push (res); int now; while (!Queue.empty ()) { now = Queue.front (); Queue.pop (); for (int i = 1; i <= M; i++) { if (now + size[i] <= N && (!visit[size[i] + now])) { visit[size[i] + now] = true; dis[now + size[i]] = dis[now] + 1; Queue.push (now + size[i]); } if (now - size[i] > 0 && (!visit[now - size[i]])) { visit[now - size[i]] = true; dis[now - size[i]] = dis[now] + 1; Queue.push (now - size[i]); } } } } class Net_Flow_Type { private : struct Edge_Date { int from; int to; int flow; int next; int cost; } edge[Max << 2]; int Edge_Count; int edge_list[Max]; int deep[Max]; int pre[Max]; public : void Prepare () { Edge_Count = 1; } inline void AddEdge (int from, int to, int flow, int cost) { Edge_Count++; edge[Edge_Count].from = from; edge[Edge_Count].to = to; edge[Edge_Count].flow = flow; edge[Edge_Count].cost = cost; edge[Edge_Count].next = edge_list[from]; edge_list[from] = Edge_Count; Edge_Count++; edge[Edge_Count].from = to; edge[Edge_Count].to = from; edge[Edge_Count].flow = 0; edge[Edge_Count].cost = -cost; edge[Edge_Count].next = edge_list[to]; edge_list[to] = Edge_Count; } bool Spfa () { for (int i = 0; i <= T; i++) deep[i] = INF; std :: queue <int> Queue; memset (visit, false, sizeof visit); Queue.push (S); deep[S] = 0; visit[S] = true; int now; while (!Queue.empty ()) { now = Queue.front (); Queue.pop (); for (int i = edge_list[now]; i; i = edge[i].next) if (edge[i].flow && deep[now] + edge[i].cost < deep[edge[i].to]) { deep[edge[i].to] = deep[now] + edge[i].cost; pre[edge[i].to] = i; if (!visit[edge[i].to]) { visit[edge[i].to] = true; Queue.push (edge[i].to); } } visit[now] = false; } return deep[T] < INF; } void Dinic () { while (Spfa ()) { int res = INF; for (int i = pre[T]; i; i = pre[edge[i].from]) res = Z :: min (res, edge[i].flow); for (int i = pre[T]; i; i = pre[edge[i].from]) { edge[i].flow -= res; edge[i ^ 1].flow += res; Answer += edge[i].cost * res; } } } void Insert_Edges () { int o = 0; for (int i = 1; i <= Count; i++) { AddEdge (S, i, 1, 0); AddEdge (i + Count, T, 1, 0); } for (int i = 1; i <= Count; i++) for (int j = 1; j <= Count; j++) if (i != j && cost[i][j] != INF) AddEdge (i, j + Count, 1, cost[i][j]); } }; Net_Flow_Type Make; int main (int argc, char *argv[]) { freopen ("password.in", "r", stdin); freopen ("password.out", "w", stdout); Z :: read (N); Z :: read (K); Z :: read (M); N++; Make.Prepare (); for (int i = 1; i <= K; i++) { Z :: read (key[i]); date[key[i]] = 1; } for (int i = 1; i <= M; i++) Z :: read (size[i]); for (int i = N; i; i--) date[i] ^= date[i - 1]; for (int i = 1; i <= N; i++) if (date[i]) number[i] = ++Count; for (int i = 1; i <= N; i++) if (date[i]) { Bfs (i); for (int j = 1; j <= N; j++) { if (!number[j]) continue; if (!visit[j]) cost[number[i]][number[j]] = INF; else cost[number[i]][number[j]] = dis[j]; } } Make.Insert_Edges (); Make.Dinic (); printf ("%d", (Answer >> 1)); return 0; }