一道神题……
rzO 发现立杰在初三（http://hi.baidu.com/wjbzbmr/item/4a50c7d8a8114911d78ed0a9据此可以推断）就怒A了此题…… Orz
/*************************************************************
我这种大弱菜，看了题目后完全茫然。
看了剧透后往网络流方向想，结果还是不会T_T。
然后去看题解，还是不会T_T。
然后去看题解的题解，还是不会T_T。
然后想了一个晚上，第二天才有点明白T_T。
上述题解在这里
**************************************************************/
题解【sol】：
请先观摩观摩来自安徽省合肥一中的梅诗珂犇的题解。衷心感谢！
【
Binary Cat Club (SGU 395)解题报告
安徽省合肥一中梅诗珂
题目大意：有关于一场聚会的N条记录，每条记录的格式有 ， ， 三种，分别表示进来一个叫”name”的人，出去一个叫”name”的人，当前聚会厅有visitors个人。现在记录的一部分遗失，但剩下记录的顺序是原顺序。给出剩下的记录，请添加最少条数的记录，使之合理化。注意：可以有人进出会厅多次，可以有人聚会结束待在会厅。
约束条件： 1≤N≤200 , 每条 记录中的visitors不超过100。
分析：
首先要明确什么是”合理”,可以看出”合理”有两条要求：
1） 对同一个人，其对应的记录应以 开头，第2个(如果有)一定是 ，第3个(如果有)一定是,交错出现。
2） 任何时候 必须与当前在场人数相同。
显然，不同的人之间互不影响。为了做到第一个要求，我们设关于某人的记录出现的
位置为a1<a2<a3<…<am。分3种情况:
1) ai对应的记录是,ai+1对应的记录是 ，那么我们一定要在ai到ai+1之间插入(当ai+1不存在时可不插入)。
2) ai对应记录 ，ai+1对应的记录是 ，那么有两种可能，一种是中间不插入任何关于name的记录，另一种是插入依次插入 ，如果把 看成左括号， 看成右括号，则两种形式为()和()()。
3） ai对应记录 ，ai+1对应记录 ，那么我们要在ai到ai+1之间插
入 。
其实完全可能插入更多的操作，但这样必然会产生完全由新插入的操作组成的
“()”,我们完全可以把其中的name替换成一个从没有出现过的新名字(而逆向替换可
能是非法的)。因此这样考虑简化了问题。
为了达到第二个目标，我们考虑补充一些“新人”，我们可以让所有“新人”的名
字都不相同。
问题转化为：合理选择已有人的 ， 操作插入位置，并插入若干“新
人”,从而使任何时候记录真实。
要考虑的情况很多，但是由恰好与visitors相同，想到带上下界的网络流，问题就
不难解决。
设有N1个 记录，对第i(1≤i≤N1)，从i点向i+1点连一条上下界皆为
visitors的边，得到的链称为“主链”。
我们要对每一种情况，设计一种结构，“安装”到主链上。
第1种： 设ai在第v个 ，和第v+1个 之间，ai+1在u，（u+1）之间，新建一个点p，从p向v连边(1,1)表示已有的 记录，v到u之间的点向p连边(0,1)表示要插入一个 记录。如下图所示(括号中的第一个数表示下界，第二个表示上界，下同)：
第2种： 设ai在第v个 ，和第v+1个 之间，ai+1在u，（u+1）之间。新建点p,q，从p向v连边(1,1)表示已有的 记录，(v+1)到u之间的点向p连边(0,1)（注：应为p向(v+1)到u之间的点连边(0,1)），从u向q连边(1,1)表示已有的 记录，v到(u-1)之间的点向q连边(0,1)，从q向p连边(1,2)，表示中间可能还会插入一个“)(”。如下图所示：
第3种： 设ai在第u个 ，和第(u+1)个 之间，ai-1在v，（v+1）之间。新建点q，从u向q连边(1,1) 表示已有的 记录，q向v到u之间的点连边(0,1)表示待插入的 。如下图所示:
（缺了张图）
还要考虑“新人”的插入，我们对主链上的每个点v，新建一个点v’,表示新人的出现在第(v-1)个 ，与第v个 之间，从v’向v连边(0,∞)表示在此处可以插入任意多个新人,从(v+1)到(N1+1)向v’连边(0,∞)表示这些新人对应的 记录。如下图所示：
完成构图，我们只要对其求最小费用可行流即可，由上面论述正确性显然。我们来分析复杂度，主链上有N1个点，对剩下的每个点加上新人对应的点共有(N+ N1)个点，非主链的N个点向主链上每个点各连一条边，最多有 条边，因此我们要对 个点， 条边的图求最小费用流，是可以接受的。
总结：本题的难点是构造出的图并没有源汇，求的也不是最大流，与NOI2008的《志愿者招募》类似，这与大多数网络流问题不同，显示了网络流模型的灵活。在建模过程中有一些小知识：比如串联求最小值，并联求和，点提供一个流量平衡方程，边提供流量限制，想让一条边不出现在最小割中，只需让其容量为无穷大。建立的模型也有几类：如有源汇的最大流，最小费用最大流，带上下界最大(小)流，无源汇最小(大)费用流。提高建模水平，只能靠多练习，解决了问题多推广。】
//
然后我再补充几个细节：
对于上述的第2种，即+-的情况，似乎有一个bug，就是我们没法保证流出来的结果一定是+- or +-+-，可能会出现++--。不过没关系，我们可以把中间的+-看作是新人。为了方便，可以在最前面加一个= 0对于第一个为-的情况，可以当作是--来处理，也就是在每个名字操作序列的最前面加-。对于最后一个为+的情况，可以当作是++来处理，也就是在每个名字操作序列的最后面加+。对于新人和最后一个为+的情况，如果是散场的时候可以不用增加费用。输出的处理：我们可以将整个操作序列合起来处理，对于某个人单独记录这个人的操作序列已经处理到的位置。对于原有操作就等到循环到了它的时候再输出，对于新增的操作则处理到的时候就输出，不用考虑顺序问题。P.S 这题我只在sgu395上交过，没有在BZ上交（因为我不是高富帅……交不起）。
附上AC代码和对拍程序
#include <cstdio> #include <queue> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <string> #include <map> void TLE(){while(1);} using std::vector; using std::string; using std::map; using std::cout; using std::endl; const int N = 800 + 9; char name[100]; map<string,int>namelist; struct Operation { bool type; int idx; string name; }oper[201][201]; struct Edge{int link,next;}es[N*N*2]; int n,equals,Vc,src,sink,cap[N][N],low[N][N],cost[N][N],dis[N],ec,son[N],opers[N],pre[N],equal[N],new_people,stcap[N][N],delta[N],cnt,name_cnt,type[N],idx[201][201],ans; vector<string> Out[N]; const string shenben[14]={"wjmzbmr","sevenkplus","acrush","fjxmlhx","lydrainbowcat","fotile","vfleaking","seter","cxjyxxme","hyn","mzn","acaeroligh","thcdusman","black"}; string now("a"); void getnext(string &s) { int len = s.size() - 1; while (len >= 0 && s[len] == 'z') s[len--] = 'a'; if (len < 0) s = "a" + s; else ++s[len]; } string newname() { while (name_cnt < 14 && namelist[shenben[name_cnt]]) ++name_cnt; if (name_cnt >= 14) { while (namelist[now]) getnext(now); namelist[now] = 1; return now; } namelist[shenben[name_cnt]] = 1; return shenben[name_cnt]; } inline void addedge(const int x,const int y) { es[++ec].link = y; es[ec].next = son[x]; son[x] = ec; } bool SPFA() { static bool inq[N]; static std::queue<int> q; memset(dis,0x3f,sizeof dis); inq[src] = 1; dis[src] = 0; for (q.push(src); !q.empty(); q.pop()) { const int u = q.front(); inq[u] = 0; for (int i = son[u]; i; i = es[i].next) { const int v = es[i].link; if (cap[u][v] && dis[v] > dis[u] + cost[u][v]) { pre[v] = u; dis[v] = dis[u] + cost[u][v]; if (!inq[v]) inq[v] = 1, q.push(v); } } } return dis[sink] != 0x3f3f3f3f; } int Cost_Flow() { int ans = 0; while (SPFA()) { int Min = 0x7ffffff; for (int i = sink; i != src; i = pre[i]) Min = std::min(Min,cap[pre[i]][i]); for (int i = sink; i != src; i = pre[i]) cap[pre[i]][i] -= Min,cap[i][pre[i]] += Min; ans += Min * dis[sink]; } return ans; } void build_graph() { for (int i = 1; i <= equals; ++i) low[i - 1][i] = cap[i - 1][i] = equal[i]; //会有重边 for (int k = 1; k <= cnt; ++k) { //oper[j][0].type = 0; // 0 --> '-' oper[k][opers[k] + 1].type = 1; // 1 --> '+' oper[k][opers[k] + 1].idx = equals; for (int i = 0; i <= opers[k]; ++i) { const int t1 = oper[k][i].type,t2 = oper[k][i + 1].type; /******************************** ++ *********************************/ if (t1 == 1 && t2 == 1) { const int u = oper[k][i].idx, v = oper[k][i + 1].idx; low[Vc][u] += 1; cap[Vc][u] += 1; for (int j = u; j <= v; ++j) { cap[j][Vc] += 1; if (i != opers[k] || j != v) cost[j][Vc] += 1; } idx[k][i] = Vc++; /******************************** -- *********************************/ }else if (t2 == 0 && t1 == 0) { const int u = oper[k][i].idx, v = oper[k][i + 1].idx; low[v][Vc] += 1; cap[v][Vc] += 1; for (int j = u; j <= v; ++j) cap[Vc][j] += 1,cost[Vc][j] += 1; idx[k][i] = Vc++; /******************************** +- *********************************/ }else if (t1 == 1 && t2 == 0) { const int u = oper[k][i].idx, v = oper[k][i + 1].idx; low[Vc + 1][Vc] += 1; cap[Vc + 1][Vc] += 2; low[Vc][u] += 1; cap[Vc][u] += 1; for (int j = u; j <= v; ++j) cap[Vc][j] += 1,cost[Vc][j] += 1; idx[k][i] = Vc++; low[v][Vc] += 1; cap[v][Vc] += 1; for (int j = u; j <= v; ++j) cap[j][Vc] += 1,cost[j][Vc] += 1; idx[k][i + 1] = Vc++; } } } new_people = Vc; for (int i = 0; i < equals; ++i) { cap[Vc][i] = 10000; //每次最多50人 200 * 50 = 10000 cost[Vc][i] = 1; for (int j = i + 1; j <= equals; ++j) { cap[j][Vc] = 10000; if (j != equals) cost[j][Vc] = 1;//可以不出去 } ++Vc; } for (int i = 0; i < Vc; ++i) for (int j = 0; j < Vc; ++j) if (cap[i][j]) { if (cost[i][j]) cost[j][i] = -cost[i][j];//cost只会一边有值(新图) addedge(i,j); if (!cap[j][i]) addedge(j,i); } memcpy(stcap,cap,sizeof cap); /************************ rebuild_graph ************************/ for (int i = 0; i < Vc; ++i) for (int j = 0; j < Vc; ++j) if (low[i][j]) { delta[i] -= low[i][j]; delta[j] += low[i][j]; cap[i][j] -= low[i][j]; } src = Vc++; sink = Vc++; for (int i = 0; i < Vc - 2; ++i) if (delta[i] > 0) cap[src][i] = delta[i],addedge(src,i),addedge(i,src); else cap[i][sink] = - delta[i],addedge(i,sink),addedge(sink,i); /************************ rebuild_graph ************************/ } void out_procedure() { static bool tag[201][201]; /************************ Get_Extra_Net ************************/ for (int i = 0; i < Vc; ++i) for (int j = 0; j < Vc; ++j) if (low[i][j]) cap[i][j] += low[i][j]; /************************ Get_Extra_Net ************************/ for (int ii = 1; ii <= type[0]; ++ii) { const int j = type[ii]/201, k = type[ii] 1,i = idx[j][k]; if (tag[j][k]) Out[oper[j][k].idx].push_back("- " + oper[j][k].name); /************************** ++ ***************************/ if (oper[j][k].type == 1 && oper[j][k + 1].type == 1) { Out[oper[j][k].idx].push_back("+ " + oper[j][k].name); for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l) if (cap[l][i] != stcap[l][i]) { if (cost[l][i]) Out[l].push_back("- " + oper[j][k].name); break; } } /************************** -- ***************************/ else if (oper[j][k].type == 0 && oper[j][k + 1].type == 0) { for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l) if (cap[i][l] != stcap[i][l]) { Out[l].push_back("+ " + oper[j][k + 1].name); break; } tag[j][k + 1] = 1; //Out[oper[j][k + 1].idx].push_back("- " + oper[j][k + 1].name);//必须后加//出事了!! } /************************** +- ***************************/ else if (oper[j][k].type == 1 && oper[j][k + 1].type == 0) { Out[oper[j][k].idx].push_back("+ " + oper[j][k].name); int mem1 = -1,mem2 = -1; for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l) if (cap[i][l] != stcap[i][l]) {mem2 = l;break;}//+ for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l) if (cap[l][i + 1] != stcap[l][i + 1]) {mem1 = l;break;}//- if (mem1 != -1 || mem2 != -1) { if (mem1 <= mem2) { Out[mem1].push_back("- " + oper[j][k].name); Out[mem2].push_back("+ " + oper[j][k].name); }else { string tmp = newname(); Out[mem2].push_back("+ " + tmp); Out[mem1].push_back("- " + tmp); } } //Out[oper[j][k + 1].idx].push_back("- " + oper[j][k].name);//出事了!! tag[j][k + 1] = 1; } } static string tmp[10001];int st; for (int i = new_people; i < Vc; ++i) { if (cap[i][i - new_people] != stcap[i][i - new_people]) { st = 0; for (int j = cap[i][i - new_people]; j < stcap[i][i - new_people]; ++j) { tmp[++st] = newname(); Out[i - new_people].push_back("+ " + tmp[st]); } }else continue; for (int j = i - new_people + 1; j < equals; ++j) for (int k = cap[j][i]; k != stcap[j][i]; ++k) Out[j].push_back("- " + tmp[st--]); } int test = 0; for (int i = 0; i <= equals; ++i) { if (i) printf("= %d\n",equal[i]); test += Out[i].size(); for (vector<string>::iterator iter = Out[i].begin(); iter != Out[i].end(); ++iter) cout << *iter << endl; } //if (test + equals != ans) TLE(); } int main() { #ifndef ONLINE_JUDGE freopen("395.in","r",stdin); freopen("395.out","w",stdout); #endif scanf("%d",&n); //equal[0] = 0; for (int i = 1,x; i <= n; ++i) { char opt; scanf("\n%c",&opt); if (opt == '=') { scanf("%d",&x); equal[++equals] = x; }else { scanf("%s",name); int t,mem = cnt; if (!namelist[string(name)]) namelist[string(name)] = ++cnt; t = namelist[string(name)]; oper[t][++opers[t]].type = (opt == '+'); oper[t][opers[t]].name = name; oper[t][opers[t]].idx = equals; if (cnt != mem) type[++type[0]] = t * 201 + 0; type[++type[0]] = t * 201 + opers[t]; // for output } } Vc = equals + 1; build_graph(); ans = Cost_Flow() + n; printf("%d\n",ans); out_procedure(); }对拍程序：
使用说明：返回值为1则答案错误。0为正确。
#include <cstdio> #include <cstring> #include <string> #include <map> FILE *f1; FILE *f2; FILE *f3; using std::map; using std::string; map<string,int>Map; char s2[201][30]; int n,m,ans; int main() { f1 = fopen("395_std.out","r"); f2 = fopen("395.out","r"); f3 = fopen("395.in","r"); fscanf(f1,"%d",&ans); fscanf(f2,"%d\n",&n); fscanf(f3,"%d\n",&m); for (int i = 1; i <= m; ++i) fgets(s2[i],100,f3); if (ans != n) return 1; char name[30],s1[30]; int cnt = 0,j = 1; for (int i = 1; i <= n; ++i) { fgets(s1,100,f2); if (j <= m && strcmp(s1,s2[j]) == 0) ++j; if (s1[0] == '=') { int x; sscanf(s1,"= %d",&x); if (x != cnt) return 1; }else if (s1[0] == '+') { sscanf(s1,"+ %s",name); if (++Map[string(name)] > 1) return 1; ++cnt; }else if (s1[0] == '-') { sscanf(s1,"- %s",name); if (!Map[string(name)]--) return 1; --cnt; } } if (j != m + 1) return 1; fclose(f1);fclose(f2);fclose(f3); }Checker.bat
@echo off:loopdata.exe395.exe395_std.exechecker.exeif not errorlevel 1 ( ping -n 2 127.1>nul echo correct goto loop)pausegoto loop
转载于:https://www.cnblogs.com/lazycal/p/sgu-395.html
