Topcoder srm496 div2 1000【最小表示法】
寒假真是悠闲了一个寒假。。。现在写代码什么都不会了 。。。今天开始写写TC
250，500都很水
1000分是一个找子串个数的题：求用小写字母组成的长度为N，并且包含至少K个长度为M的回文串的不同连续子串，的字符串的个数
第一次写1000分的题，想了一阵子，不知道怎么排除重复的字符串。看了别人的报告，学习了大神们的写法
大意是，用搜索找出一种字符串模式，用C个字母表示整个字符串可能的最小表示法：
如：可能有aaa,bbb,ccc,ddd.....zzz那么全可以用aaa表示
dfs(int pos,int C)
{
if(pos==N)if(check())ans+=calc(C);
REP(i,C)Rec[pos]=i,dfs(pos+1,max(C,i+1));
}
dfs的含义是：找出当前位置为pos，之前的出现过的数字最大为C的字符串。
当pos==N时，判断是否合法
若合法，加上该最小表示的字符串所包含的字符串个数,既：26个字符放入C个空的全排列数
【带花树专题】
PS:...我还是不懂什么是带花树，就只能套套模板了。
下面是几个带花树的题...目前只能找到这点。
Ural-1099 Work scheduling 难度：*
http://acm.timus.ru/problem.aspx?space=1&num=1099
大意：有N个士兵，每个士兵可以另一个士兵巡逻，给出M组士兵愿意在一起巡逻，求出最大的士兵配置方案。
分析：直接求最大匹配就好了，然后输出所有的组合
ZJU 3316 Game 难度：**
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3316
大意：有N个棋子在棋盘上，2个人轮流拿走一个棋子，第一步可以拿任意一个，而之后每一步必须拿上一步拿走的棋子曼哈顿长度L以内的棋子，问，后手是否能赢
分析：把每一个棋子与周围距离为L的棋子都连上边后，形成一些联通块。易知，一轮游戏只能在某一个联通块里开始直到结束。那么，如果有一个联通块不是完美匹配，先手就可以走那个没被匹配到的点，后手不论怎么走，都必然走到一个被匹配的点上，先手就可以顺着这个交错路走下去，最后一定是后手没有路可走，因为如果还有路可走，这一条交错路，就是一个增广路，必然有更大的匹配。
总结：判断是否是完美匹配。
HDU 3446 daizhenyang's chess 难度：***
http://acm.hdu.edu.cn/showproblem.php?pid=3446
大意：有一个R*C的棋盘，棋盘上有一些格子是幸运的格子，棋盘上只有一个棋子：king。king有一定的走路范围：20个格子如题中图所示。两个人轮流走，每个人可以移动king走到没被走过的幸运的格子上。问，先手是否能赢。
分析：这题与上一题某方面是一样的。都是与增广路有关。把所有能连的边先连上，我们先不算king，求一次匹配。然后我们再算上king，求一次匹配。如果第二次匹配的结果比第一次大，说至少明存在一条增广路，且增广路的起点为king所在的点，那么，我们沿着这条路走下去，最后后手必然无路可走。
总结：2次匹配。
HDU 3551 hard problem 难度：****
http://acm.hdu.edu.cn/showproblem.php?pid=3551
大意：给出一个无向图，并给出一个子图的每个点的度数，问是否能去掉一些边，得到这个子图。
分析：因为我们要求出这样的一个子图，是删去一些边，使其度数减少，所以，我们先把每条边拆成2个点，(u,e)和(e,v)，这两个点连一条边，若匹配这条边表示边e(u,v)不被删除，然后我们把每个点拆成deg[i]-D[i]个点（deg[i]为原图度数，D[i]为子图度数），然后对所有该点和他的边(i,e)组成的点连一条边，表示这个点缺少的度数，可以由这儿得到。接着，求匹配，如果是完美匹配，即：每个度数都找到了可以使他减少的边。这个子图可以得到。
总结：让每个需要减少的度数匹配到该点所连接的一条边。
下面是我自己用的带花树的模板，暂时没有出现问题：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXE 250*250*2
#define MAXN 250
#define SET(a,b) memset(a,b,sizeof(a))
deque<int> Q;
//g[i][j]存放关系图：i,j是否有边,match[i]存放i所匹配的点
bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN];
int match[MAXN],pre[MAXN],base[MAXN];
//找公共祖先
int findancestor(int u,int v)
{
bool inpath[MAXN]={false};
while(1)
{
u=base[u];
inpath[u]=true;
if(match[u]==-1)break;
u=pre[match[u]];
}
while(1)
{
v=base[v];
if(inpath[v])return v;
v=pre[match[v]];
}
}
//压缩花
void reset(int u,int anc)
{
while(u!=anc)
{
int v=match[u];
inblossom[base[u]]=1;
inblossom[base[v]]=1;
v=pre[v];
if(base[v]!=anc)pre[v]=match[u];
u=v;
}
}
void contract(int u,int v,int n)
{
int anc=findancestor(u,v);
SET(inblossom,0);
reset(u,anc);reset(v,anc);
if(base[u]!=anc)pre[u]=v;
if(base[v]!=anc)pre[v]=u;
for(int i=1;i<=n;i++)
if(inblossom[base[i]])
{
base[i]=anc;
if(!inque[i])
{
Q.push_back(i);
inque[i]=1;
}
}
}
bool dfs(int S,int n)
{
for(int i=0;i<=n;i++)pre[i]=-1,inque[i]=0,base[i]=i;
Q.clear();Q.push_back(S);inque[S]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop_front();
for(int v=1;v<=n;v++)
{
if(g[u][v]&&base[v]!=base[u]&&match[u]!=v)
{
if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n);
else if(pre[v]==-1)
{
pre[v]=u;
if(match[v]!=-1)Q.push_back(match[v]),inque[match[v]]=1;
else
{
u=v;
while(u!=-1)
{
v=pre[u];
int w=match[v];
match[u]=v;
match[v]=u;
u=w;
}
return true;
}
}
}
}
}
return false;
}
int solve(int n)
{
SET(match,-1);
int ans=0;
for(int i=1;i<=n;i++)
if(match[i]==-1&&dfs(i,n))
ans++;
return ans;
}
上下界最大流，最小流
这里只记录一下最大，最小流求法，暂不写理论证明
1.新源S'给每个点加一条容量为《流入的下界总和》的边
2.新汇T'给每个点加一条容量为《流出的下界总和》的边。
若最小流:
求一次S'->T'最大流，T->S add inf 再求一次 S'->T'最大流
若满流，可行
T->S的流量为最小流，各边流量+下界为最小流各边实际流量
若最大流:
T->S add inf 求一次最大流
若满流，可行
去掉T->S的边（我感觉用sap应该不要去也可以？？待验证 (成功一次，理论上没问题)）
求S->T最大流，结果为最大流，各边流量+下界为最大流实际流量
ps:如果是无源无汇的话，直接求一次最大流就可以了
（待纠错，mark）
pku 3635 Full Tank? - bfs+优先队列
题目大意：有N个站点，每个站点供应油的价格为Pi，有M条路，每条路耗油量为Ci。现在又Q个询问，求出，当坦克在S点，油量为0，要到达T点，油箱容量为V的最小价格。
分析：有点像dij，用一个数组used[ i ][ j ]记录，第i个站点，油量为j的情况是否出现过。用优先队列每次选出花费最小的节点更新。入队有2种情况：
1.当可以走向下一个节点时
2.当可以再买1升汽油时（保证每种情况都考虑到，DP的思想）
PS：代码写烂了...好慢
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
#define MAXE 20020
#define MAXN 1010
#define SET(a,b) memset(a,b,sizeof(a))
int next[MAXE],p[MAXE],c[MAXE],st[MAXN],e;
int used[MAXN][110],price[MAXN];
void add(int a,int b,int d)
{
next[e]=st[a];
p[e]=b;
c[e]=d;
st[a]=e++;
}
struct Node
{
int num,fuel,cost;
Node(int num,int fuel,int cost):num(num),fuel(fuel),cost(cost){}
friend bool operator < (Node a,Node b)
{
return a.cost>b.cost;
}
};
int work(int S,int T,int C)
{
priority_queue<Node> Q;
SET(used,0);
Q.push(Node(S,0,0));
used[S][0]=1;
while(!Q.empty())
{
int u=Q.top().num,f=Q.top().fuel,m=Q.top().cost;
if(u==T)return m;
Q.pop();
for(int v=st[u];v!=-1;v=next[v])
{
if(f>=c[v])
{
if(!used[p[v]][f-c[v]])
{
used[p[v]][f-c[v]]=1;
Q.push(Node(p[v],f-c[v],m));
}
}
}
if(f+1<=C&&!used[u][f+1])Q.push(Node(u,f+1,m+price[u]));
}
return -1;
}
int main()
{
int N,M;
SET(st,-1);e=0;
scanf("%d%d",&N,&M);
int i,j,k;
for(i=1;i<=N;i++)scanf("%d",price+i);
for(i=1;i<=M;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++,y++;
add(x,y,z);
add(y,x,z);
}
int P;
scanf("%d",&P);
for(i=1;i<=P;i++)
{
int S,T,C;
scanf("%d%d%d",&C,&S,&T);
S++,T++;
int tttt=work(S,T,C);
if(tttt==-1)printf("impossible\n");
else printf("%d\n",tttt);
}
//system("pause");
return 0;
}
PKU 3621-Sightseeing Cows [分数规划/spfa]
题目大意：有一个单向图，可以从任意一点出发，回到该点，每条路都会耗费一定的时间ti。每到一个新的点都会得到一定的分数fi。求一条路使得∑fi/∑ti最大。
题目分析：我们设最优解经过的城市为环 n1->n2->...nk->n1，我们可以猜测最优解的路上不会重复经过一个点(除去出发点)。简略证明：
假设一个非出发点k被重复经过了，那么k点至少连接了两个环。我们设第一个环的解为:x1 = F1/T1 ，第二个环的解为:x2 = F2/T2。总的解为: x3 = (F1+F2-fk)/(T1+T2)<max(x1,x2)。
那么最优解为 x' = (fn1+fn2+.....fnk)/(e(n1,n2),e(n2,n3)+....e(nk,n1))。 x' = F/T -> T * x' - F = 0。
为了求解出这个最优值x'，我们设函数 g(x)=T*x-F。这是一个单调函数。所以可以用二分求出答案。
/*
简略证明：
我们设T(y),F(y)为函数（当y不同，表示选取不同的环），设x1<x2，y1 为使 g(x1) 取得最小值的解选择，则：
g(x1) = max(T(y) * x1 - F(y)) = T(y1) * x1 - F(y1) < T(y1)*x2 - F(y1) <=max( T(y)*x2 - F(y) ) = g(x2)
*/
当g(x)>0时，x > x'
当g(x)<0时，x < x'
当g(x)=0时，x = x'
我们可以改变所有边权为 : t*x-f，用spfa求解是否存在负环（g(x)<0），存在增大x，否则减小x
我们把所有没松弛过的点，当成源点，spfa一次...但这题似乎直接对1点松弛也过了，是数据问题？？
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 1010
#define MAXE 5050
#define inf 1000000000.0
#define SET(a,b) memset(a,b,sizeof(a))
#define EPS 1e-3
int next[MAXE],p[MAXE],st[MAXN],e;
double dis[MAXN],f[MAXN],c[MAXE];
int used[MAXN],cnt[MAXN];
void add(int a,int b,double d)
{
next[e]=st[a];
p[e]=b;
c[e]=d;
st[a]=e++;
}
bool spfa(double mid,int S,int N)
{
int i,j,k;
queue<int> Q;
for(i=1;i<=N;i++){
dis[i]=inf;
used[i]=0;
}
dis[S]=0.0;Q.push(S);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
used[u]=0;
for(int v=st[u];v!=-1;v=next[v])
{
double w=c[v]*mid-f[p[v]];
if(dis[p[v]]-dis[u]-w>-EPS)
{
dis[p[v]]=dis[u]+w;
if(!used[p[v]])
{
used[p[v]]=1;
cnt[p[v]]++;
if(cnt[p[v]]>N)return true;
Q.push(p[v]);
}
}
}
}
return false;
}
int main()
{
SET(st,-1);e=0;
int N,M;
scanf("%d%d",&N,&M);
int i,j,k;
double l=0,r=0;
for(i=1;i<=N;i++)
{
scanf("%lf",f+i);
r+=f[i];
}
for(i=1;i<=M;i++)
{
int x,y;
double z;
scanf("%d%d%lf",&x,&y,&z);
add(x,y,z);
}
while(r-l>EPS)
{
double mid=(l+r)/2;
SET(cnt,0);
bool flag=false;
for(i=1;i<=N;i++)
if(!cnt[i])
{
flag=spfa(mid,i,N);
if(flag)break;
}
if(flag)l=mid;
else r=mid;
}
printf("%.2f\n",l);
return 0;
}