DD的SGU之旅

串中的每个数字都属于gcd(N,K)个循环中的一个，求每个循环的“最大表示”（跟最小表示一样，只不过是找字典序最大的，改一个不等号就可以了）中最大的输出。最小表示的求法可以用周源论文里的非常精巧的线性算法。
[code:cpp]
#include
#include
using namespace std;

const int maxn=150001;
struct str{
int n;
char s[maxn];
char& operator[](int i){
return s[i];
}
const char& operator[](int i)const{
return s[i];
}
str():n(0){}
};
char s[maxn];
bool vis[maxn];
int N,K;

bool compare(const str& cur,int i,int j,int& p){
for(p=0;pcur[y];
}
}
return true;
}
void largest(const str& cur,str& res){
int i=0,j=1,p;
while(jb[i];
return false;
}
int main(){
scanf("%d %d\n",&N,&K);
K%=N;
gets(s);
str res;
memset(vis,0,sizeof(vis));
for(int i=0;i
if(vis[i])continue;
str now;
int j=i;
while(!vis[j]){
vis[j]=true;
now[now.n++]=s[j];
j+=K;
j%=N;
}
str cur;
largest(now,cur);
if(larger(cur,res))
res=cur;
}
for(int i=0,j=0;i
if(j==res.n)
j=0;
putchar(res[j]);
}
putchar('\n');
}
[/code]

237是一道很不错的DP题。状态定义成两部分：v(i,j)表示s[i..j]变成回文串的最小长度，w(i,j)表示这个回文串的最小字典序（若v(i,j)!=∞才有定义）。每次更新的时候若长度相等就需要比较字典序。状态转移方程就是分左右是普通字母、'?'、'*'来讨论（'!'在输入时就替换成三个'?'），在程序里很清楚。0.5s的时限很紧，我做了很多的常数优化才AC（甚至包括把inline函数改成macro），主要是要尽量减少strcpy、strcmp的次数。空间上需要用滚动数组来优化。
[code:cpp]
#include
#include
using namespace std;

const int maxn=256*3;
char s[maxn];
int _v[4][maxn];
#define v(i,j) (_v[((j)-(i))&3][(i)])
char _w[4][maxn][maxn*2];
#define w(i,j) (_w[((j)-(i))&3][(i)])
int N;

void input(){
N=0;
for(; {
char c=getchar();
if(c=='\n'||c==EOF)
break;
if(c=='!'){
s[++N]='?';
s[++N]='?';
s[++N]='?';
}
else
s[++N]=c;
}
}
inline void update(int& o,int x,char* os,const char* xs){
if(o>x||(o==x&&strcmp(os,xs)>0)){
o=x;
strcpy(os,xs);
}
}
inline void update(int& o,int x,char* os,char first,const char* mid){
bool to=false;
if(o>x+2)
to=true;
else if(o==x+2){
if(os[0]>first)
to=true;
else if(os[0]==first){
os[o-1]=0;
if(strcmp(os+1,mid)>0)
to=true;
os[o-1]=os[0];
}
}
if(to){
o=x+2;
os[0]=first;
strcpy(os+1,mid);
os[o-1]=first;
os[o]=0;
}
}
void solve(int l,int r){
if(l==r){
if(s[l]=='*'){
v(l,l)=0;
w(l,l)[0]=0;
}
else{
v(l,l)=1;
w(l,l)[0]=(s[r]=='?'?'a':s[r]);
w(l,l)[1]=0;
}
return;
}
int& res=v(l,r)=2000000000;
char* str=w(l,r);
if(s[l]=='*'){
if(s[r]=='*'){
update(res,v(l+1,r),str,w(l+1,r));
update(res,v(l,r-1),str,w(l,r-1));
}
else{
update(res,v(l,r-1),str,(s[r]=='?'?'a':s[r]),w(l,r-1));
update(res,v(l+1,r),str,w(l+1,r));
}
}
else if(s[l]=='?'){
if(s[r]=='*'){
update(res,v(l+1,r),str,'a',w(l+1,r));
update(res,v(l,r-1),str,w(l,r-1));
}
else{
update(res,v(l+1,r-1),str,(s[r]=='?'?'a':s[r]),w(l+1,r-1));
}
}
else{
if(s[r]=='*'){
update(res,v(l+1,r),str,s[l],w(l+1,r));
update(res,v(l,r-1),str,w(l,r-1));
}
else if(s[r]==s[l]||s[r]=='?'){
update(res,v(l+1,r-1),str,s[l],w(l+1,r-1));
}
}
}
int main(){
input();
memset(_v,0,sizeof(_v));
for(int d=0;d
for(int i=1;i+d<=N;++i){
solve(i,i+d);
}
}
if(v(1,N)==2000000000)
puts("NO");
else{
puts("YES");
puts(w(1,N));
}
}
[/code]

这个题目的标准做法似乎是线段树，来实现动态的查找“第K根线段是哪个”。不过我刚看到这个题的时候不知怎么的想用平衡树维护不相交区间做这个题，但事实上这在实际效率和编程复杂度上都是不如线段树的，毕竟写个Buttom-Up的Splay得费点功夫，像我这种代码拖沓的要想把Splay、Insert、Remove、Find、Select、Prev、Next都实现了得两百行……用了重载operator new这种比较高深的东西，简单说就是预先分配一大块空间然后每次new的时候取一个出来而不是让系统动态的分配空间，这样做（对于极限数据）在时间和空间上都能略微有所优化，不过要记住重载了operator new以后要不就把operator delete也给重载了，要不就别用delete。要记住，写Splay的时候，每个操作中都要有Splay（一般就是把那个返回的指针Splay一下），才能保证时间复杂度。
[code:cpp]
#include
#include
using namespace std;

const int maxn=1000002;
int cells[maxn];

struct Tower{
int beg,end;//两端
long long total;//总数
Tower(int beg=0,int end=0,int total=0):
beg(beg),end(end),total(total){}
void merge(const Tower& rhs){
if(rhs.begend)
end=rhs.end;
total+=rhs.total;
}
};
inline bool operator<(const Tower& l,const Tower& r){ return l.end < r.beg; } typedef Tower Key; struct Node{ Key key; Node *left,*right,*par; int size;//这个子树的节点总数 Node(Key _key); void resize(); void* operator new(size_t); }*NullNode,*Root; Node* data; Node::Node(Key _key=Key()): key(_key),left(NullNode),right(NullNode),par(NullNode),size(1){} void Node::resize(){ size=1; size+=left->size;
size+=right->size;
}
inline void* Node: perator new(size_t){
return (void*)data++;
}

void Init(){
data=(Node*)new char[maxn*sizeof(Node)];
NullNode = new Node();
NullNode->left = NullNode->right = NullNode->par = NullNode;
NullNode->size = 0;
Root = NullNode;
}
void LeftRotate(Node* Cur){
Node* Par = Cur->par;
Node* Anc = Par->par;
Par->left = Cur->right;
if(Par->left!=NullNode)
Par->left->par = Par;
Cur->right = Par;
Cur->right->par = Cur;
if(Anc!=NullNode){
if( Anc->left == Par )
Anc->left = Cur;
else
Anc->right = Cur;
}
Cur->par = Anc;
Par->resize();
Cur->resize();
if(Anc!=NullNode)
Anc->resize();
}
void RightRotate(Node* Cur){
Node* Par = Cur->par;
Node* Anc = Par->par;
Par->right = Cur->left;
if(Par->right!=NullNode)
Par->right->par = Par;
Cur->left = Par;
Cur->left->par = Cur;
if(Anc!=NullNode){
if( Anc->right == Par )
Anc->right = Cur;
else
Anc->left = Cur;
}
Cur->par = Anc;
Par->resize();
Cur->resize();
if(Anc!=NullNode)
Anc->resize();
}
void Splay(Node* Cur){
while( Cur->par != NullNode ){
Node* Par = Cur->par;
Node* Anc = Par->par;
if( Anc == NullNode ){
if( Par->left == Cur )
LeftRotate(Cur);
else
RightRotate(Cur);
}
else if( Anc->left == Par ){
if( Par->left == Cur ){
LeftRotate(Par);
LeftRotate(Cur);
}
else{
RightRotate(Cur);
LeftRotate(Cur);
}
}
else{
if( Par->right == Cur ){
RightRotate(Par);
RightRotate(Cur);
}
else{
LeftRotate(Cur);
RightRotate(Cur);
}
}
}
Root = Cur;
}
Node* Find( const Key& key, Node* Cur=Root ){
for(; {
if( key < Cur->key ){
if( Cur->left == NullNode )
break;
Cur = Cur->left;
}
else if( Cur->key < key ){ if( Cur->right == NullNode )
break;
Cur = Cur->right;
}
else break;
}
Splay(Cur);
return Cur;
}
void Insert( const Key& key ){
if( Root == NullNode ){
Root = new Node(key);
return;
}
Find(key);
Node* Cur = new Node(key);
if( key < Root->key ){
Cur->left = Root->left;
if(Cur->left != NullNode){
Cur->left->par = Cur;
Root->left = NullNode;
}
Cur->right = Root;
Cur->right->par = Cur;
Cur->right->resize();
}
else{
Cur->right = Root->right;
if(Cur->right != NullNode){
Cur->right->par = Cur;
Root->right = NullNode;
}
Cur->left = Root;
Cur->left->par = Cur;
Cur->left->resize();
}
Cur->resize();
Root = Cur;
}
void Remove( Node* Cur ){
Splay(Cur);
if( Cur->left == NullNode ){
Root = Cur->right;
if(Root)
Root->par = NullNode;
}
else{
Cur->left->par = NullNode;
Find(Cur->key,Cur->left);
Root->right = Cur->right;
if( Root->right != NullNode )
Root->right->par = Root;
Root->resize();
}
//delete Cur;
}
Node* Select( int rank, Node* Cur=Root ){
--rank;
for(; {
if( rank == Cur->left->size )
break;
if( rank < Cur->left->size )
Cur = Cur->left;
else{
rank -= (Cur->left->size+1);
Cur = Cur->right;
}
}
Splay(Cur);
return Cur;
}
Node* Prev( const Key& key ){
Find(key);
Node* Cur=Root;
if( Cur->key < key ) return Cur; Cur = Cur->left;
while( Cur->right != NullNode )
Cur = Cur->right;
return Cur;
}
Node* Next( const Key& key ){
Find(key);
Node* Cur=Root;
if( key < Cur->key )
return Cur;
Cur = Cur->right;
while( Cur->left != NullNode )
Cur = Cur->left;
return Cur;
}

void put(int x,int c){
if(c==0)return;
cells[x]+=c;
if(cells[x]==c){
Tower tower(x,x,c);
if(cells[x-1]){
Node* prev = Prev(tower);
tower.merge(prev->key);
Remove(prev);
}
if(cells[x+1]){
Node* next = Next(tower);
tower.merge(next->key);
Remove(next);
}
Insert(tower);
}
else{
Node* Cur = Find(Tower(x,x,c));
Cur->key.total += c;
}
}
void tput(int t,int x,int c){
Node* Cur = Select(t);
Cur->key.total += c;
cells[Cur->key.beg + x-1] += c;
}
void towers(){
printf("%d towers\n",Root->size);
}
void cubes(int t){
printf("%lld",Select(t)->key.total);
printf(" cubes in %dth tower\n",t);
}
void length(int t){
Node* Cur = Select(t);
printf("length of %dth tower is %d\n",t,Cur->key.end - Cur->key.beg + 1);
}
void tcubes(int t,int x){
printf("%d cubes in %dth column of %dth tower\n",cells[Select(t)->key.beg + x-1],x,t);
}
int main(){
int N;
scanf("%d\n",&N);
char q[10];
int a,b,c;
memset(cells,0,sizeof(cells));
Init();
while(N--){
scanf("%s %d %d %d\n",q,&a,&b,&c);
if(q[0]=='t'){
if(q[1]=='p')
tput(a,b,c);
else if(q[1]=='o')
towers();
else if(q[1]=='c')
tcubes(a,b);
}
else if(q[0]=='p')
put(a,b);
else if(q[0]=='c')
cubes(a);
else if(q[0]=='l')
length(a);
}
}
[/code]

这个题目令人联想到匹配，都是求一个两组事物间的对应关系，只不过一个学生只能对应一个学校，一个学校至少要对应两个学生，所以说用网络流来解。学生和学校都抽象成顶点，图中每一条源->学生->学校->汇的路径代表一个学生与一个学校的对应关系。源和每个学生连一条边，上界为1（一个学生只能对应一个学校）；每个学生到他喜欢的学校连一条边，上界为1；每个学校和汇连一条边，下界为2（一个学校至少要对应两个学生）。需要求解的是一个有上下界的可行流问题。可以看出，如果这个流网络中存在可行流，则一定存在流量为2*k的可行流。所以说从汇到源连一个上界为2*k的边，就转化成了无源汇的无源汇的可行流问题，可以用194的方法求解。这样解出来事实上是一个满足要求的最小流，每个学校恰有两个学生。
[code:cpp]
#include
#include
#include
#include
using namespace std;

const int maxn=512;
struct edge{
int x,y;
int c,f;
edge *next,*back;
edge(int x,int y,int c,edge* next):
x(x),y(y),c(c),f(0),next(next){}
}*E[maxn];
int n,k;
int N,S,T;

void addedge(int a,int b,int c){
E[a]=new edge(a,b,c,E[a]);
E[b]=new edge(b,a,0,E[b]);
E[a]->back = E[b];
E[b]->back = E[a];
}
//源：0。学生：1..n。学校：n+1..n+k。汇n+k+1。附加源：n+k+2，附加汇：n+k+3
//源跟学生连边，上界1。学生跟喜欢的学校连边，上界1。学校跟汇连边，下界1。汇跟源连边上界2k。
void input(){
memset(E,0,sizeof(E));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) addedge(0,i,1); for(int i=1;i<=n;++i){ int count; scanf("%d",&count); while(count--!=0){ int d; scanf("%d",&d); addedge(i,n+d,1); } } for(int i=1;i<=k;++i){ addedge(n+i,n+k+3,2); } addedge(n+k+2,n+k+1,2*k); addedge(n+k+1,0,2*k); S=n+k+2; T=n+k+3; N=n+k+3; } int D[maxn]; void init_distance_label(){ int queue[maxn],head=0,tail=0; queue[tail++]=T; memset(D,-1,sizeof(D)); D[T]=0; for(;;){ int v=queue[head++]; for(edge* e=E[v];e;e=e->next){
if(e->c!=0)continue;
int y=e->y;
if(D[y]==-1){
D[y]=D[v]+1;
queue[tail++]=y;
}
}
if(head==tail)
break;
}
}
void flow(){
init_distance_label();
edge* cur[maxn];
memcpy(cur,E,sizeof(E));
edge* path[maxn];
int path_n=0;
int i=S;
for(; {
if(i==T){
int delta=INT_MAX,mink;
for(int k=0;k c < delta){ delta=path[k]->c;
mink=k;
}
for(int k=0;k c -= delta;
path[k]->f += delta;
path[k]->back->c += delta;
path[k]->back->f -= delta;
}
path_n=mink;
i=path[path_n]->x;
}
edge* e;
for(e=cur[i];e;e=e->next){
if(e->c==0)continue;
int j=e->y;
if(D[i]==D[j]+1)
break;
}
if(e){
cur[i]=e;
path[path_n++]=e;
i=e->y;
}
else{
int minlabel=N;
for(edge* e=E[i];e;e=e->next){
if(e->c==0)continue;
int j=e->y;
if(D[j]x;
else if(D[i]>N)
break;
}
}
}
bool possible(){
for(edge* e=E[S];e;e=e->next){
if(e->c!=0)
return false;
}
return true;
}
void output(bool suc){
if(!suc){
puts("NO");
exit(0);
}
puts("YES");
for(int i=1;i<=k;++i){ putchar('2'); for(edge* e=E[n+i];e;e=e->next){
if(e->f < 0) printf(" %d",e->y);
}
putchar('\n');
}
}
int main(){
input();
flow();
output(possible());
}
[/code]

一个流网络，某些边必须充满，求其最小流。这事实上是一个有上下界的最小流的特例。求解的方法是这样的：如果在原图的汇和源之间连一条边，就转换成了有上下界的无源汇的可行流（194）这样的问题，只是这条边的最小容量（也就是答案）是未知的，所以可以采用二分答案的方法，二分这条边的容量，然后判断是否有解即可。注意最小的可行流可能是零流（也就是没有任何边需要充满的情况），所以二分答案时的下界需要注意。
[code:cpp]
#include
#include
#include
#include
using namespace std;

const int maxn=256;
struct edge{
int x,y;
int f;//流量
int c;//上界减下界
int num;//编号
edge *next,*back;
edge(int x,int y,int c,int num,edge* next):
x(x),y(y),f(0),c(c),num(num),next(next){}
}*E[maxn],*key;
int N,M;
int ans[maxn*maxn];
int S,T;//附加源0，附加汇N+1
int D[maxn];//距离标号，即点到汇点的最少的弧数
int W[maxn];//流入的下界总和减去流出的下界总和

void addedge(int a,int b,int c,int i){
E[a]=new edge(a,b,c,i,E[a]);
E[b]=new edge(b,a,0,0,E[b]);
E[a]->back=E[b];
E[b]->back=E[a];
}
void input(){
scanf("%d%d",&N,&M);
memset(W,0,sizeof(W));
memset(E,0,sizeof(E));
memset(ans,0,sizeof(ans));
for(int i=1;i<=M;++i){ int a,b,d,x; scanf("%d%d%d%d",&a,&b,&d,&x); if(!x){ addedge(a,b,d,i); } else{ ans[i]+=d; W[b]+=d; W[a]-=d; } } S=0; T=N+1; for(int i=1;i<=N;++i){ if(W[i]>0)
addedge(S,i,W[i],0);
else if(W[i]<0) addedge(i,T,-W[i],0); } addedge(N,1,0,0); key=E[N]; } void init_distance_label(){//就是从汇点开始，只走容量为0的边的一次广搜 int queue[maxn],head=0,tail=0; queue[tail++]=S; memset(D,-1,sizeof(D)); D[T]=0; for(;;){ int v=queue[head++]; for(edge* e=E[v];e;e=e->next){
if(e->c!=0)continue;
int y=e->y;
if(D[y]==-1){
D[y]=D[v]+1;
queue[tail++]=y;
}
}
if(head==tail)
break;
}
}
void flow(){
init_distance_label();
edge* path[maxn];
edge* current[maxn];
memcpy(current,E,sizeof(E));
int path_n=0;
int i=S;
for(; {
if(i==T){
int min=INT_MAX,mink;
for(int k=0;k c < min){ min=path[k]->c;
mink=k;
}
}
for(int k=0;k c -= min;
path[k]->back->c += min;
path[k]->f += min;
path[k]->back->f = -(path[k]->f);
}
path_n=mink;
i=path[path_n]->x;
}
edge* e;
for(e=current[i];e;e=e->next){
if(e->c==0)continue;
int j=e->y;
if(D[i]==D[j]+1)
break;
}
if(e){//e就是从i出发的允许弧
current[i]=e;//前面的都不是允许弧，所以下次从这里开始找就可以
path[path_n++]=e;
i=e->y;
}
else{//从i出发没有允许弧，需要修改标号
int minlabel=N;
for(edge* e=E[i];e;e=e->next){
if(e->c==0)continue;
int j=e->y;
if(D[j]x;
}
else if(D[i]>N)//此时已经没有从源点到汇点的路了
break;
}
}
}
bool possible(){
for(edge* e=E[S];e;e=e->next){
if(e->c!=0)
return false;
}
for(edge* e=E[T];e;e=e->next){
if(e->back->c!=0)
return false;
}
return true;
}
void output(bool suc=true){
if(!suc){
puts("Impossible");
exit(0);
}
printf("%d\n",key->c + key->f);
printf("%d",ans[1]);
for(int i=2;i<=M;++i) printf(" %d",ans[i]); putchar('\n'); } bool check(int value){ N+=2; for(int i=0;inext){
e->c += e->f;
e->f = 0;
}
key->c = value;
flow();
N-=2;
return possible();
}
void solve(){
int lo=-1,hi=1000000;//lo必须是-1，因为答案有可能是零流
if(!check(hi))
output(false);
for(; {
int mid=(lo+hi)/2;
if(check(mid))
hi=mid;
else
lo=mid;
if(hi-lo==1){
check(hi);
break;
}
}
for(int i=1;i<=N;++i){ for(edge* e=E[i];e;e=e->next)
ans[e->num]+=e->f;
}
}
int main(){
input();
solve();
output();
}
[/code]

这个问题是这样的：已知一组形如X[i]>=X[j]+C的不等式（C非负），求一组解（或者判断无解），并要求X[N]-X[1]最小。将所有变量抽象成顶点，每个不等式对应一个由点i到点j的权为C的边。如果图中存在非零的环，说明不等式组中存在矛盾，无解。零环代表这些变量完全等价，所以可以将图收缩强连通分量，就成了DAG，可以用拓扑排序的方法求最长距离。也就是按照拓扑序考察边，确保约束得到满足。对图进行一次拓扑排序得到的是每个变量的最小取值，在反向图（这时每个顶点对应的是变量的相反数）中进行拓扑排序可以得到变量的最大取值。如果某个变量的最大取值小于最小取值，也会无解。为了保证X[N]-X[1]最小，可以用X[1]的最大值在原图中再用一次拓扑排序进行更新，就得到了满足要求的解。这本质上是差分约束系统问题，但由于所有边权非负，所以可以缩环变成DAG，从而用拓扑排序线性复杂度地求解。
[code:cpp]
#include
#include
#include
using namespace std;

const int maxn=10001;
struct edge{
int y,w;
edge* next;
edge(int y,int w,edge* next):
y(y),w(w),next(next){}
}*E[maxn],*_E[maxn];
int N;
int belong[maxn];//缩圈以后属于的强连通分量

void input(){
int m;
scanf("%d%d",&N,&m);
memset(E,0,sizeof(E));
memset(_E,0,sizeof(_E));
for(int i=0;inext){
int y=e->y;
if(!vis[y])
dfs(y);
}
order[count++]=x;
}
void _dfs(int x,int root){
belong[x]=root;
for(edge* e=_E[x];e;e=e->next){
int y=e->y;
if(belong[y]==0)
_dfs(y,root);
}
}
void mergeedge(edge *E[]){
edge* last[maxn];
for(int i=1;i<=N;++i){ if(E[i]==0) last[i]=0; else for(edge* e=E[i];;e=e->next){
if(e->next==0){
last[i]=e;
break;
}
}
}
for(int i=1;i<=N;++i){ if(belong[i]==i)continue; if(last[i]==0)continue; int j=belong[i]; if(last[j]==0) E[j]=E[i]; else last[j]->next=E[i];
last[j]=last[i];
E[i]=0;
}
for(int i=1;i<=N;++i){ for(edge* e=E[i];e;e=e->next)
e->y=belong[e->y];
}
}
void shrink(){
memset(vis,0,sizeof(vis));
count=0;
for(int i=1;i<=N;++i){ if(!vis[i]) dfs(i); } memset(belong,0,sizeof(belong)); for(int i=N-1;i>=0;--i){
int x=order[i];
if(belong[x]==0){
_dfs(x,x);
}
}
mergeedge(E);
mergeedge(_E);
}
bool possible(){
for(int x=1;x<=N;++x){ if(belong[x]!=x)continue; for(edge* e=E[x];e;e=e->next){
if(e->y==x&&e->w!=0)
return false;
}
}
return true;
}
void topo(edge *E[],int dis[maxn]){
int in[maxn];
memset(in,0,sizeof(in));
for(int x=1;x<=N;++x){ for(edge* e=E[x];e;e=e->next){
int y=e->y;
if(y!=x)//缩圈后的图中可能有自环
++in[y];
}
}
int Q[maxn],head=0,tail=0;
for(int x=1;x<=N;++x){ if(x!=belong[x])continue; if(in[x]==0) Q[tail++]=x; } for(;;){ if(head==tail) break; int x=Q[head++]; for(edge* e=E[x];e;e=e->next){
int y=e->y;
if(dis[x]+e->w>dis[y])
dis[y]=dis[x]+e->w;
if(--in[y]==0)
Q[tail++]=y;
}
}
for(int i=1;i<=N;++i) dis[i]=dis[belong[i]]; } int MinDis[maxn],MaxDis[maxn]; void output(bool); void solve(){ shrink(); if(!possible()) output(false); for(int i=1;i<=N;++i){ MinDis[i]=-10000; MaxDis[i]=-10000; } topo(E,MinDis); topo(_E,MaxDis); for(int i=N;i>=1;--i){
if(-MaxDis[i]
output(false);
}
MinDis[belong[1]]=-MaxDis[belong[1]];
topo(E,MinDis);
}
void output(bool suc){
if(!suc){
puts("-1");
exit(0);
}
printf("%d",MinDis[1]);
for(int i=2;i<=N;++i)
printf(" %d",MinDis[i]);
putchar('\n');
}
int main(){
input();
solve();
output(true);
}
[/code]

这个题目是无源汇的有上下界的可行流问题。增加源汇，输入中的每条边(a,b,l,c)拆成三条边：a到b容量为c-l的边，S到a的容量为l的边，b到T的容量为l的边。当然，可以把每个点到源和汇的所有边都合并成一条，也就是记录每个顶点流入的下界总和减去流出的下界总和，如果大于0就连源，小于0就连汇。题目的点数是200，边数没有说明，用Edmonds-Karp会超时（也许是我的EK写得烂的缘故），用我以前写的距离标号增广可以167ms AC。
[code:cpp]
#include
#include
#include
#include
using namespace std;

const int maxn=256;
struct edge{
int x,y;
int f;//流量
int c;//上界减下界
int num;//编号
edge *next,*back;
edge(int x,int y,int c,int num,edge* next):
x(x),y(y),f(0),c(c),num(num),next(next){}
}*E[maxn];
int N,M;
int ans[maxn*maxn];
int S,T;//附加源0，附加汇N+1
int D[maxn];//距离标号，即点到汇点的最少的弧数

void addedge(int a,int b,int c,int i){
E[a]=new edge(a,b,c,i,E[a]);
E[b]=new edge(b,a,0,0,E[b]);
E[a]->back=E[b];
E[b]->back=E[a];
}
void input(){
scanf("%d%d",&N,&M);
int W[maxn];//流入的下界总和减去流出的下界总和
memset(W,0,sizeof(W));
memset(E,0,sizeof(E));
memset(ans,0,sizeof(ans));
for(int i=1;i<=M;++i){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); addedge(a,b,d-c,i); ans[i]+=c; W[b]+=c; W[a]-=c; } S=0; T=N+1; for(int i=1;i<=N;++i){ if(W[i]>0)
addedge(S,i,W[i],0);
else if(W[i]<0) addedge(i,T,-W[i],0); } } void init_distance_label(){//就是从汇点开始，只走容量为0的边的一次广搜 int queue[maxn],head=0,tail=0; queue[tail++]=T; memset(D,-1,sizeof(D)); D[T]=0; for(;;){ int v=queue[head++]; for(edge* e=E[v];e;e=e->next){
if(e->c!=0)continue;
int y=e->y;
if(D[y]==-1){
D[y]=D[v]+1;
queue[tail++]=y;
}
}
if(head==tail)
break;
}
}
void flow(){
init_distance_label();
edge* path[maxn];
edge* current[maxn];
memcpy(current,E,sizeof(E));
int path_n=0;
int i=S;
for(; {
if(i==T){
int min=INT_MAX,mink;
for(int k=0;k c < min){ min=path[k]->c;
mink=k;
}
}
for(int k=0;k c -= min;
path[k]->back->c += min;
path[k]->f += min;
path[k]->back->f = -(path[k]->f);
}
path_n=mink;
i=path[path_n]->x;
}
edge* e;
for(e=current[i];e;e=e->next){
if(e->c==0)continue;
int j=e->y;
if(D[i]==D[j]+1)
break;
}
if(e){//e就是从i出发的允许弧
current[i]=e;//前面的都不是允许弧，所以下次从这里开始找就可以
path[path_n++]=e;
i=e->y;
}
else{//从i出发没有允许弧，需要修改标号
int minlabel=N;
for(edge* e=E[i];e;e=e->next){
if(e->c==0)continue;
int j=e->y;
if(D[j]x;
}
else if(D[i]>N)//此时已经没有从源点到汇点的路了
break;
}
}
}
bool possible(){
for(edge* e=E[S];e;e=e->next){
if(e->c!=0)
return false;
}
for(edge* e=E[T];e;e=e->next){
if(e->back->c!=0)
return false;
}
return true;
}
void output(bool suc=true){
if(!suc){
puts("NO");
exit(0);
}
puts("YES");
for(int i=1;i<=M;++i) printf("%d\n",ans[i]); } void solve(){ N+=2; flow(); N-=2; if(!possible()) output(false); for(int i=1;i<=N;++i){ for(edge* e=E[i];e;e=e->next)
ans[e->num]+=e->f;
}
}
int main(){
input();
solve();
output();
}
[/code]

这个题目的意思是：给定一个图以及两个点集A、B，求若干条从A中顶点到B中顶点的路径，这些路径没有重复的顶点，每条路径的长度都等于从A中顶点到B中顶点的最短长度，且这个路径的集合是极大的（也就是说无法在保留所有这些路径的前提下找到新的合法路径）。需要用到的就是距离标号或者分层图的思想，A中顶点距离标号为0，然后用一遍BFS给其它点距离标号，显然所求路径的边都要在按照距离标号确定的分层图里。然后，由于要求的是极大路径集合，所以可以用DFS找路径，找至不能再找就可以了，我觉得我的程序中那个非递归的DFS实现还是比较优美的。如果需要求的是最大的路径集合，就得在分层图上添加源汇求最大流了，流量限制在点上，拆点为边即可。
[code:cpp]
#include
#include
#include
using namespace std;

const int maxn=10001;
struct edge{
int y;
edge* next;
edge(int y,edge* next):
y(y),next(next){}
}*E[maxn],*Path[maxn];
int N;
int A[maxn],N1;
int B[maxn],N2;
int dis[maxn];
bool vis[maxn];
int P,K;

void input(){
int m;
scanf("%d%d",&N,&m);

memset(E,0,sizeof(E));
for(int i=0;inext){
int y=e->y;
if(dis[y]==-1){
dis[y]=dis[x]+1;
Q[tail++]=y;
}
}
}
}
void DFS(){
P=0;
memset(vis,0,sizeof(vis));
for(int i=0;inext){
int y=e->y;
if(vis[y])continue;
if(dis[y]!=dis[x]-1)continue;
cur=new edge(y,cur);
x=y;
break;
}
if(E[x]==0){
cur=cur->next;
if(cur==0)
break;
x=cur->y;
}
}
}
}
void solve(){
BFS();
K=INT_MAX;
for(int i=0;i

y);
for(edge* e=Path[i]->next;e;e=e->next){
printf(" %d",e->y);
}
putchar('\n');
}
}
int main(){
input();
solve();
output();
}
[/code]

这个题目就是所谓的“稳定婚姻系统”，使用的是“延迟认可算法”。算法是这样的：任选一位没有配偶的男生X，考察当前没有拒绝他的女生中他最喜欢的那个女生Y，若Y没有配偶或者Y喜欢X更甚于她当前的配偶，则X和Y（暂时）结成配偶，否则Y会拒绝X，重复以上过程，直至所有男生都有配偶。这个算法的正确性是很容易证明的（反证法即可）。事实上是不存在输出NO的情况的，因为不可能有哪位男生被所有的女生拒绝。具体实现的时候，每个男生按照喜欢程度从大到小保存一个他喜欢的女生的列表，再用一个指针记录当前列表中没有拒绝他的下一个女生，这样就可以在O(1)的时间内找到女生Y。再用一个队列保存当前没有配偶的男生，初始时全部男生都在队列里，这样就可以在O(1)的时间内找到男生X，当原先有配偶的女生Y转投男生X是，他原先的配偶被加到队列里。这样实现的话，“拒绝”最多发生O(N^2)次，所以主算法的运行时间是O(N^2)。但这道题最耗时的部分是预处理，我终于体会到C++的string无法忍受的龟速了，I/O还好说，不用stream就可以，可没想到string::compare也要比strcmp慢那么多，实在是让人难以接受。我把原来用string写的TLE程序中的输入输出换成C-Style，再把所有可能出现的string::compare换成strcmp就AC了。不过最后我把程序改成了完全不用string。
[code:cpp]
#include
#include
#include
using namespace std;

const int maxn=801,maxl=12;
char *BoyName[maxn],*GirlName[maxn];
char BoyData[maxn][maxn][maxl],GirlData[maxn][maxn][maxl];
int GirlOrder[maxn][maxn];//GirlOrder[i][j]表示Girl[i]心中对Boy[j]的排位
int BoyList[maxn][maxn];//每个Boy按照喜欢程度排序的Girl列表
int BoyChoose[maxn],GirlChoose[maxn];
int N;

void input(){
scanf("%d\n",&N);
for(int i=0;i<=N;++j){ scanf("%s",BoyData[i][j]); } } for(int i=0;i<=N;++j){ scanf("%s",GirlData[i][j]); } } } int BinarySearch(const char* x,char *name[]){ if(name[0]==x) return 0; int lo=0,hi=N; for(;;){ int mid=(lo+hi)/2; int d=strcmp(x,name[mid]); if(d<0) hi=mid; else if(d>0)
lo=mid;
else
return mid;
}
}
int compare(const void* a,const void* b){
return strcmp(*((char**)a),*((char**)b));
}
void init(){
qsort(BoyName,N,sizeof(char*),compare);
qsort(GirlName,N,sizeof(char*),compare);
for(int i=0;i
int x=BinarySearch(BoyData[i][0],BoyName);
for(int j=1;j<=N;++j){
int y=BinarySearch(BoyData[i][j],GirlName);
BoyList[x][j-1]=y;
}
}
for(int i=0;i
int x=BinarySearch(GirlData[i][0],GirlName);
for(int j=1;j<=N;++j){
int y=BinarySearch(GirlData[i][j],BoyName);
GirlOrder[x][y]=j;
}
}
}
int BoySet[maxn];
int Q[maxn*maxn],head=0,tail=0;
bool solve(){
memset(BoySet,0,sizeof(BoySet));
memset(BoyChoose,-1,sizeof(BoyChoose));
memset(GirlChoose,-1,sizeof(GirlChoose));
for(int i=0;i
Q[tail++]=i;
for(; {
if(head==tail)
return true;
int i=Q[head++];
for(; {
if(BoySet[i]==N)
return false;
int j=BoyList[i][BoySet[i]++];
if(GirlChoose[j]==-1){
BoyChoose[i]=j;
GirlChoose[j]=i;
break;
}
else if(GirlOrder[j][i]
BoyChoose[i]=j;
BoyChoose[GirlChoose[j]]=-1;
Q[tail++]=GirlChoose[j];
GirlChoose[j]=i;
break;
}
}
}
}
void output(){
for(int i=0;i
printf("%s %s\n",BoyName[i],GirlName[BoyChoose[i]]);
}
int main(){
input();
init();
if(solve()){
puts("YES");
output();
}
else
puts("That Won't Happen");
}
[/code]