[JSOI2010]满汉全席

Time Limit:10000MS  Memory Limit:65536K
Total Submit:34 Accepted:21
Case Time Limit:1000MS

Description

满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在數量繁多的菜色之中。由于菜色众多而繁杂，只有极少數博学多闻技 艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。
世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会，将 于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在參赛的厨师之中，找到满汉料理界的明日之星。
大会的规则如下：每位參赛的选手可以得到n 种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。大会的评审制度是：共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的見解，但基本见解是，要有兩样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式 的涮羊肉锅，就不能算是满汉全席。但避免过于有主見的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下，才能淘汰一位选手，否则 不能淘汰一位參赛者。换句话說，只要參赛者能在这兩种材料的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉，羊肉和牛肉时，有四位评 审员的喜好如下表：
评审一 评审二 评审三 评审四
满式牛肉 满式猪肉 汉式牛肉 汉式牛肉
汉式猪肉 满式羊肉 汉式猪肉 满式羊肉
如參赛者甲做出满式猪肉，满式羊肉和满式牛肉料理，他将无法满足评审三的要求，无法通过评审。而參赛者乙做出汉式猪肉，满式羊肉和满式牛肉料理， 就可以满足所有评审的要求。
但大会后來发现，在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话，所有的參赛者最多只能通过部分评审员的审查而不是全部，所以可能 会发生没有人通过考核的情形。如有四个评审员喜好如下表时，则不論參赛者采取什么样的做法，都不可能通过所有评审的考核：
评审一 评审二 评审三 评审四
满式羊肉 满式猪肉 汉式羊肉 汉式羊肉
汉式猪肉 满式羊肉 汉式猪肉 满式猪肉
所以大会希望有人能写一个程序來判断，所选出的m 位评审，会不会发生 没有人能通过考核的窘境，以便协会组织合适的评审团。

Input

第一行包含一个数字 K，代表测试文件包含了K 组资料。每一组测试资料的第一行包含兩个数字n 跟m（n≤100，m≤1000），代表有n 种材料，m 位评审员。为方便起見，材料舍弃中文名称而给予编号，编号分别从1 到n。接下來的m 行，每行都代表对应的评审员所拥有的兩个喜好，每个喜好由一个英文字母跟一个数字代表，如m1 代表这个评审喜欢第1 个材料透过满式料理做出來的菜，而h2 代表这个评审员喜欢第2 个材料透过汉式料理做出來的菜。每个测试文件不会有超过50 组测试资料，而每笔测试资料中材料的种类数跟评审员的个数均不超过15。

Output

每笔测试资料输出一行，如果不会发生没有人能通过考核的窘境，输出GOOD；否则输出BAD（大写字母）。

Sample Input

2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2

Sample Output

GOOD
BAD

Source

JSOI2010第二轮Contest2
水题啊。。一眼就看出是2-sat，而且还不需要方案囧。。直接构图然后Tarjan就可以了。。
具体说就是对每个菜建两个节点，一个节点连向另一节点表示选了这个就一定要选那个，比如一个人要求一个汉一个满，如果第一个选了满那么第二个只能是汉了(*^__^*) 。。然后看看有没有两个矛盾的量在一个强联通分量里的就可以了囧。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<stack>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100*2;
struct Edge
{
int t;Edge*next;
Edge(int _t,Edge* _next):t(_t),next(_next){}
}*E[maxn]={0};
void AddEdge(int s,int t){E[s]=new Edge(t,E[s]);}
int n,m;
inline int node(int i,bool j){return i*2+j;}
int low[maxn],ord[maxn],id[maxn],cnt,snt;bool instack[maxn];
stack<int> S;
int dfs(int x)
{
low[x]=ord[x]=++cnt;
S.push(x);instack[x]=true;
for(Edge*e=E[x];e;e=e->next)
if(!ord[e->t]) low[x]=min(low[x],dfs(e->t));
else if(instack[e->t]) low[x]=min(low[x],ord[e->t]);
if(low[x]==ord[x])
{
int u;
do{u=S.top();S.pop();id[u]=snt;instack[u]=false;}while(u!=x);
snt++;
}
return low[x];
}
void Tarjan()
{
memset(ord,0,sizeof(ord));
memset(instack,0,sizeof(instack));
cnt=snt=0;
rep(i,2*n)if(!ord[i])dfs(i);
}
bool Judge()
{
rep(i,n) if(id[2*i]==id[2*i+1])return false;
return true;
}
void solve()
{
scanf("%d %dn",&n,&m);bool c[2];int x[2];char t;
memset(E,0,sizeof(E));
while(m–)
{
rep(i,2)scanf("%c%dn",&t,x+i),–x[i],c[i]=t==’h’;
rep(i,2) AddEdge(node(x[i],!c[i]),node(x[1-i],c[1-i]));
}
Tarjan();
if(Judge())cout<<"GOOD"<<endl;
else cout<<"BAD"<<endl;
}
int main()
{
//freopen("in","r",stdin);
int t;cin>>t;while(t–)solve();
}

www.vijos.cn/Problem_Show.asp
话说Vijos的很多题目都有点问题，这个明显有多解的但连解的要求的没有说囧。。
这是经典剪枝问题了。。我欺负题的数据比较小，随便写了几个剪枝就过了(*^__^*)
首先是所有数一定要递增，如果不递增的话更改操作顺序是可以改成递增的，那就没必要重复搜索了。替代性剪枝
其次如果当前最大数超过需要的数了，最优性剪枝。
使用DFSID，如果还能迭代d次，当前最大数*2^d次方小于n，可行性剪枝。
同时搜索的时候从后往前搜数，更快逼近答案。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100;
int n;
int A[maxn];
bool dfs(int p,int d)
{
if(!d)return false;
if(A[p-1]>n||(A[p-1]<<d)<n)return false;
if(A[p-1]==n)return true;
for(int i=p-1;i>=0;–i)
for(int j=i;j>=0;–j)
{
int x=A[i]+A[j];
if(x<=A[p-1])break;
A[p]=x;
if(dfs(p+1,d-1))return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;A[0]=1;
for(int i=1;;i++)
if(dfs(1,i))
{
cout<<i<<endl;
rep(j,i)cout<<A[j]<<" ";
cout<<endl;
break;
}
}

[NOI2006]最大获利

Time Limit:5000MS  Memory Limit:65536K
Total Submit:65 Accepted:36
Case Time Limit:1000MS

Description

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要 做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需 要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1≤i≤N）。
另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N）
THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的 中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

Input

输入文件中第一行有两个正整数N和M 。
第二行中有N个整数描述每一个通讯中转站的建立成本，依次为P1, P2, …, PN 。
以下M行，第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。
所有变量的含义可以参见题目描述。

Output

你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

Sample Input

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

Sample Output

4

Hint

【样例说明】
选择建立1、2、3号中转站，则需要投入成本6，获利为10，因此得到最大收益4。
【评分方法】
本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。
【数据规模和约定】
80%的数据中：N≤200，M≤1 000。
100%的数据中：N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100。

Source

我晕。。我以前的SAP写法都是错的？zkw的程序居然是错的囧。。不过悲剧的是以前的所有题目怎么都能过囧。。NOI的数据果然是NB额。。
即使增广过了边容量已经是0了还要更新高度？我觉得没道理啊。。不过不这样就不能AC。真是活见鬼囧。。
Code：
#include<cstdio>
#include<algorithm>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=60000,inf=~0U>>1;
struct Edge
{
int t,c;
Edge(int _t,int _c,Edge* _next):
t(_t),next(_next),c(_c){}
Edge*next,*op;
}*E[maxn]={0};
int n,m,vs,vt,v,Ans=0;
void InsEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
inline int T(int i){return i;}
inline int C(int i){return n+i;}
void Init()
{
scanf("%d%d",&n,&m);int s,t,c;
v=n+m+2;vs=v-1;vt=v-2;
rep(i,n)scanf("%d",&c),InsEdge(T(i),vt,c);
rep(i,m)
{
scanf("%d%d%d",&s,&t,&c);–s;–t;
InsEdge(C(i),T(s),inf);
InsEdge(C(i),T(t),inf);
InsEdge(vs,C(i),c);
Ans+=c;
}
}
int h[maxn],vh[maxn];
int aug(int no,int m)
{
if(no==vt) return m;
int l=m,minh=v;
for(Edge*i=E[no];i;i=i->next)if(i->c)
{
if(h[no]==h[i->t]+1)
{
int d=aug(i->t,min(l,i->c));
i->c-=d,i->op->c+=d,l-=d;
if(!l||h[vs]>=v) return m-l;
}
minh=min(minh,h[i->t]+1);
}
if(!–vh[h[no]]) h[vs]=v;
vh[h[no]=minh]++;
return m-l;
}
int CalFlow()
{
memset(h,0,sizeof(h));
memset(vh,0,sizeof(vh));
vh[0]=v;int flow=0;
while(h[vs]<v) flow+=aug(vs,inf);
return flow;
}
int main()
{
//freopen("in","r",stdin);
Init();
cout<<Ans-CalFlow()<<endl;
}

[JSOI]Word Query电子字典

Time Limit:10000MS  Memory Limit:65536K
Total Submit:27 Accepted:11
Case Time Limit:1000MS

Description

人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法，而只知道该单词的一个错误的近似拼法，这时人们可能陷入困境，为了查找一个单词而浪费大 量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题：用户只要输入一个字符串，电子字典就返回与该单词编辑距离最小的几个单词供用户选 择。
字符串a与字符串b的编辑距离是指：允许对a或b串进行下列“编辑”操作，将a变为b或b变为a，最少“编辑”次数即为距离。
 删除串中某个位置的字母；
 添加一个字母到串中某个位置；
 替换串中某一位置的一个字母为另一个字母；

JSOI团队正在开发一款电子字典，你需要帮助团队实现一个用于模糊查询功能的计数部件：对于一个待查询字符串，如果它是单词，则返回-1；如果 它不是单词，则返回字典中有多少个单词与它的编辑距离为1。

Input

第一行包含两个正整数N (N < = 10,000)和M (M < = 10,000)。
接下来的N行，每行一个字符串，第i + 1行为单词Wi。单词长度在1至20之间。再接下来M行，每行一个字符串，第i + N + 1表示一个待查字符串Qi。待查字符串长度在1至20之间。Wi和Qi均由小写字母构成，文件中不包含多余空格。所有单词互不相同，但是查询字符串可能有 重复。

提示：有50%的数据范围：N < = 1,000，M < = 1,000。

Output

输出应包括M行，第i行为一个整数Xi。Xi = -1表示Qi为字典中的单词；否则Xi表示与Qi编辑距离为1的单词的个数。

Sample Input

4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

Sample Output

-1
2
3

Hint

abcd在单词表中出现过；abc与单词abcd、aabc的编辑距离都是1；abcdd与单词abcd、abcde、abced的编辑距离都是1。

Source

JSOI第二轮Contest1
61.187.179.132:8080/JudgeOnline/showproblem
额。这题目告诉我一件事情就是unsigned long long基本是不会冲突的，所以可以放心的用Hash。。直接暴力Hash了，replace的模拟是枚举每一个位置，然后枚举改变成什么，相应的在原串的Hash值+上改变量。效率是(26*Len)，
delete和Insert首先要算出从一个位置到数字首和数字尾的Hash值，然后Delete枚举位置删除就可以了，Insert还要枚举插入那个数。
总共就是(26*Len*m+Len*n)。。。速度虽然慢，还是A掉了(*^__^*)
囧。。为什么别人的程序都是20000KB+的我这个只有500而且还这么慢，悲剧。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int seed=131,maxl=20+10;
typedef unsigned long long ull;
struct Hash
{
static const int size=17771;
struct node
{
ull key;
int num;
node*next;
node(ull _key,int _num,node*_n):key(_key),num(_num),next(_n){}
}*H[size];
Hash(){memset(H,0,sizeof(H));}
int find(ull code)
{
int h=code%size;
for(node*i=H[h];i;i=i->next)if(i->key==code)return i->num;
return -1;
}
void insert(ull code,int num)
{
//cout<<"I"<<code<<endl;
int h=code%size;
H[h]=new node(code,num,H[h]);
}
}hash;
ull Code(char*s)
{
ull ret=0;
while(*s) ret*=seed,ret+=*(s++);
return ret;
}
int n,m;
void solve()
{
static ull Power[maxl];
char s[maxl];
Power[0]=1;
For(i,1,maxl-1)Power[i]=Power[i-1]*seed;
scanf("%d %d",&n,&m);
rep(i,n) scanf("%sn",s),hash.insert(Code(s),i);
ull Left[maxl],Right[maxl];
while(m–)
{
scanf("%sn",s);ull t=Code(s),x,ret=0,l=strlen(s),tmp;
set<int> S;
if(hash.find(t)!=-1){printf("-1n");continue;}
//Replace a letter
for(int i=0;i<l;i++)
{
for(char c=’a’;c<=’z’;c++)if(c!=s[i])
if((tmp=hash.find(t+Power[l-i-1]*(c-s[i])))!=-1)
S.insert(tmp);
}
//Cal the Left Hash value and the Right Hash value
Left[0]=0;
for(int i=1;i<=l;i++)
Left[i]=Left[i-1]*seed+s[i-1];
Right[l+1]=0;
for(int i=l;i>=1;i–)
Right[i]=Right[i+1]+Power[l-i]*s[i-1];
//Delete a letter
for(int i=1;i<=l;i++)
{
ull x=Left[i-1]*Power[l-i]+Right[i+1];
if((tmp=hash.find(x))!=-1)S.insert(tmp);//cout<<"D"<<endl;
}
//Insert a letter
for(int i=0;i<=l;i++)
{
ull x=Left[i]*Power[l-i+1]+Right[i+1];
for(char c=’a’;c<=’z’;c++)if((tmp=hash.find(x+Power[l-i]*c))!=-1)S.insert(tmp);//cout<<"I"<<endl;
}
printf("%dn",S.size());
}
}
int main()
{
//freopen("in","r",stdin);
solve();
}

额。。这题过的有点悬
USER: Tom Chen [45384401]
TASK: betsy
LANG: C++

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.011 secs, 2804 KB]
Test 2: TEST OK [0.000 secs, 2804 KB]
Test 3: TEST OK [0.011 secs, 2804 KB]
Test 4: TEST OK [0.011 secs, 2804 KB]
Test 5: TEST OK [0.000 secs, 2804 KB]
Test 6: TEST OK [0.022 secs, 2804 KB]
Test 7: TEST OK [0.961 secs, 2804 KB]

All tests OK.
时间卡的好紧额囧。。
我只用了两个剪枝，一个是每个除了终点之外的点要一进一出所以要记录相邻的点数，还有一个就是当前点到终点的距离如果小于剩下的点数就剪枝。。
这样都能过囧。。
Code：
/*
PROG: betsy
LANG: C++
ID: Tom Chen
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
using namespace std;
const int maxn=10,di[]={1,0,-1,0},dj[]={0,-1,0,1};
bool vis[maxn][maxn]={0};
int n,ans=0;
int C[maxn][maxn];
int ii,jj;
void show()
{
rep(i,n)
{
rep(j,n) cout<<C[i][j]<<" ";
cout<<endl;
}
}
int Put(int i,int j)
{
int ret=0;
vis[i][j]=true;
rep(d,4)
{
ii=di[d]+i,jj=dj[d]+j;
if(!vis[ii][jj]&&–C[ii][jj]<2&&(ii!=n||jj!=1))
ret++;
}
return ret;
}
void Back(int i,int j)
{
vis[i][j]=false;
rep(d,4)
{
ii=di[d]+i,jj=dj[d]+j;
if(!vis[ii][jj])
++C[ii][jj];
}
}
inline int dist(int a,int b){return a>0?a:-a+b>0?b:-b;}
void dfs(int i,int j,int c)
{
//cout<<i<<" "<<j<<" "<<c<<endl;
//show();
if(n*n-c<dist(i-n,j-1))return;
if(i==n&&j==1)
{
if(c==n*n) ans++;
return;
}
int t=Put(i,j);
if(t<=1)
{
rep(d,4)
{
ii=i+di[d],jj=j+dj[d];
if(!vis[ii][jj]&&(!t||C[ii][jj]<2))
dfs(ii,jj,c+1);
}
}
Back(i,j);
}
int main()
{
freopen("betsy.in","r",stdin);
freopen("betsy.out","w",stdout);
cin>>n;
rep(i,n+2)rep(j,n+2)vis[i][j]=true;
For(i,1,n)For(j,1,n) C[i][j]=4,vis[i][j]=false;
For(i,1,n) C[i][1]=C[1][i]=C[n][i]=C[i][n]=3;
C[1][1]=C[1][n]=C[n][1]=C[n][n]=2;
dfs(1,1,1);
cout<<ans<<endl;
}

额。。VIJOS复活了。。所以我去A了这道题。。www.vijos.cn/Problem_Show.asp
题目是说给你n个数，都小于10^5，然后让你求出其中一个子序列（连不连续无所谓，只要顺序是原序列的顺序就OK）。。 相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的，如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子，就简单了。首先算出10^5一下每个质数，然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值，然 后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的，并且预先处理也可以大大降低枚举量。。我感觉应该会很快，没想到0ms秒杀，爽额。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000+1,maxp=maxn>>3;
bool NotPrime[maxn]={0};
int Ps[maxp],cnt=0;
void GetPrime()
{
for(int i=2;i*i<maxn;i++)
{
if(!NotPrime[i])
{
for(int j=i*2;j<maxn;j+=i)
NotPrime[j]=true;
}
}
for(int i=2;i<maxn;i++)
if(!NotPrime[i])
Ps[cnt++]=i;
}
int Max[maxp],pnt,Tmp[1000];
void GetDiv(int p)
{
pnt=0;
for(int i=0;i<cnt;i++)
{
int t=Ps[i];if(t*t>p)break;
if(p%t==0)
{
Tmp[pnt++]=i;
while(p%t==0)p/=t;
}
}
if(p!=1)
{
int i=lower_bound(Ps,Ps+cnt,p)-Ps;
Tmp[pnt++]=i;
}
}
void solve()
{
int n,x;scanf("%d",&n);
while(n–)
{
scanf("%d",&x);
GetDiv(x);
int ret=0;
rep(i,pnt)ret=max(ret,Max[Tmp[i]]);
ret++;
rep(i,pnt) Max[Tmp[i]]=ret;
}
int ans=0;
rep(i,cnt) ans=max(ans,Max[i]);
printf("%dn",ans);
}
int main()
{
//freopen("in","r",stdin);
GetPrime();
solve();
}

[HAOI2008]硬币购物

Time Limit:10000MS Memory Limit:165536K
Total Submit:11 Accepted:8
Case Time Limit:1000MS

Description

硬币购物
一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。
每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

Input

第一行
c1,c2,c3,c4,tot
下面tot行
d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

Sample Output

Source
这题有点NB的，DP+容斥原理囧。。
Code:

#include<iostream>using namespace std;const int maxn=4,maxs=100000+1;typedef long long ll;ll Dp[maxs]={0};int C[maxn];void Cal(){ Dp[0]=1; for(int i=0;i<maxn;i++) for(int j=C[i];j<maxs;j++) Dp[j]+=Dp[j-C[i]];}int D[maxn];void dfs(int p,int ch,int now,ll&ret){ if(now<0) return; if(p==maxn) { if(ch&1) ret-=Dp[now]; else ret+=Dp[now]; return; } dfs(p+1,ch+1,now-C[p]*(D[p]+1),ret); dfs(p+1,ch,now,ret);}void solve(){ int s;ll ans=0;for(int i=0;i<maxn;i++)cin>>D[i]; cin>>s; dfs(0,0,s,ans); cout<<ans<<endl;}int main(){ //freopen("in","r",stdin); int t; for(int i=0;i<maxn;i++)cin>>C[i];cin>>t; Cal(); while(t–)solve();}427数据规模di,s<=100000tot<=10001 2 5 10 23 2 3 1 101000 2 2 2 900

[CQOI2009]dance跳舞

Time Limit:10000MS Memory Limit:165536K
Total Submit:35 Accepted:19
Case Time Limit:1000MS

Description

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。
有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。
给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

Input

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数，即舞曲数目的最大值。

Sample Input

Sample Output

Hint

N<=50
K<=30

Source
网络流建模真是越来越得心应手了(*^__^*) 。。这道题目很显然是要最优转判定的，比如判定能不能有T轮，怎么转呢，对每个男生建立3个定点表示全体，得到喜欢的，得到不喜欢的，那么源向全体连一条容量为T的边，全体向喜欢的连无穷大的边，全体向不喜欢的连容量为k的bian，然后女生也类似分为3个跟汇连，然后男生用喜欢节点向喜欢的女生的喜欢节点，用不喜欢节点向不喜欢的女生的不喜欢节点连容量为1连边。。就OK了。。
Code：

#include<cstdio>#include<queue>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=300+20;struct Edge{ int t,c; Edge(int _t,int _c,Edge* _next): t(_t),next(_next),c(_c){} Edge*next,*op;}*E[maxn]={0};int n,vs,vt;int h[maxn],vh[maxn],v;void InsEdge(int s,int t,int c){ //cout<<s<<" "<<t<<" "<<c<<endl; E[s]=new Edge(t,c,E[s]); E[t]=new Edge(s,0,E[t]); E[s]->op=E[t];E[t]->op=E[s];}const int All=0,Like=1,DontLike=2,inf=1<<20;inline int Boy(int x,int type){return x*3+type;}inline int Girl(int x,int type){return (n+x)*3+type;}void Init(){ int k;char x; scanf("%d %dn",&n,&k); v=n*6+2;vs=v-1;vt=v-2; rep(i,n)rep(j,n) { scanf("%cn",&x); int t=x==’Y’?Like:DontLike; InsEdge(Boy(i,t),Girl(j,t),1); } rep(i,n) { InsEdge(vs,Boy(i,All),0); InsEdge(Boy(i,All),Boy(i,Like),inf); InsEdge(Boy(i,All),Boy(i,DontLike),k); InsEdge(Girl(i,All),vt,0); InsEdge(Girl(i,Like),Girl(i,All),inf); InsEdge(Girl(i,DontLike),Girl(i,All),k); }}int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}int CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); vh[0]=v;int flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}void Work(){ int Flow=0; for(int i=1;;i++) { for(Edge*e=E[vs];e;e=e->next)e->c++; for(Edge*e=E[vt];e;e=e->next)e->op->c++; Flow+=CalFlow(); if(Flow!=i*n) { cout<<i-1<<endl; break; } }}int main(){ //freopen("in","r",stdin); Init(); Work();}33 0YYYYYYYYY

很显然首先spfa出最短路，然后就按最短路建图，然后很显然就换成了最小割的问题了囧。。不过这里的割是有向的，注意一下哦(*^__^*) 嘻嘻
Code:

#include<cstdio>#include<queue>#include<algorithm>#include<iostream>using namespace std;const int maxn=500;struct Edge{ int t,c,Len; bool e; Edge(int _t,int _Len,int _c,Edge* _next): t(_t),Len(_Len),next(_next),c(_c),e(false){} Edge*next,*op; /*void addFlow(int _c) { c-=_c; op->c+=_c; }*/}*E[maxn];int n,m,vs,vt;void InsEdge(int s,int t,int c,int Len){ E[s]=new Edge(t,Len,c,E[s]); E[t]=new Edge(s,Len,c,E[t]); E[s]->op=E[t];E[t]->op=E[s];}void Init(){ scanf("%d %d",&n,&m);int s,t,Len,c; vs=0,vt=n-1; while(m–) { scanf("%d %d %d %d",&s,&t,&Len,&c); InsEdge(s-1,t-1,c,Len); }}const int inf=~0U>>2;int DistToStart[maxn],DistToEnd[maxn];void Spfa(int Dist[maxn],int vs){ queue<int> Q; bool inQ[maxn]={0}; for(int i=0;i<n;i++) Dist[i]=inf; Dist[vs]=0;inQ[vs]=true;Q.push(vs); while(Q.size()) { int t=Q.front();Q.pop();inQ[t]=false;int cost=Dist[t]; for(Edge*i=E[t];i;i=i->next) { int ncost=cost+i->Len; if(ncost<Dist[i->t]) { Dist[i->t]=ncost; if(!inQ[i->t]) inQ[i->t]=true,Q.push(i->t); } } }}void BuildGraph(){ Spfa(DistToStart,vs); Spfa(DistToEnd,vt); int cost=DistToStart[vt]; for(int i=0;i<n;i++) for(Edge*e=E[i];e;e=e->next) if(DistToStart[i]+e->Len+DistToEnd[e->t]==cost) { e->e=true; e->op->e=true; e->op->c=0; } cout<<cost<<endl;}int h[maxn],vh[maxn],v;int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->e&&i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->e&&i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}long long CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); v=n;vh[0]=v;long long flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}int main(){ //freopen("in","r",stdin); Init(); BuildGraph(); cout<<CalFlow()<<endl;}

[SCOI2005]最大子矩阵

Time Limit:10000MS Memory Limit:165536K
Total Submit:26 Accepted:13
Case Time Limit:1000MS

Description

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

Input

第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

Output

只有一行为k个子矩阵分值之和最大为多少。

Sample Input

Sample Output

Source
这个明显要DP，一维的太水就不说了。
二维的话，首先预处理出子矩阵的和比较方便。
设Dp(i,a1,a2)为i个矩形，第1列1..a1，第二列1..a2的最大价值，
那么如果第一列的a1不放的话，是Dp(i,a1-1,a2)。。。
如果第二列的a2不放的话，是Dp(i,a1,a2-1)。。。
如果放的话枚举上一个状态是O（n）的。
然后只有在a1==a2的时候才枚举宽度为2的矩阵的情况就可以了。。
不过细节很要紧，我WA了半天，这样下去怎么行啊。比赛考到的话肯定悲剧的囧。。
Code：

#include<iostream>#include<cstring>using namespace std;const int maxn=100+10,maxk=10+1,inf=~0U>>2;int n,m,k;//solve 1inline void Renew(int&x,int c){ x=max(x,c);}void Solve1(){ int Dp[maxk][maxn]={0}; int A[maxn]={0}; for(int i=1;i<=n;i++)cin>>A[i],A[i]+=A[i-1]; for(int i=1;i<=k;i++) { for(int j=0;j<=n;j++) { int&x=Dp[i][j];x=-inf; if(j)x=Dp[i][j-1]; for(int o=0;o<j;o++) { Renew(x,Dp[i-1][o]+A[j]-A[o]); } } } cout<<Dp[k][n]<<endl;}//solve 2void Solve2(){ int Dp[maxk][maxn][maxn]={0}; int A[2][maxn]={0},S[maxn]={0}; for(int j=1;j<=n;j++) for(int i=0;i<2;i++) cin>>A[i][j],S[j]+=A[i][j],A[i][j]+=A[i][j-1]; for(int j=1;j<=n;j++) S[j]+=S[j-1]; for(int i=1;i<=k;i++) for(int a1=0;a1<=n;a1++) for(int a2=0;a2<=n;a2++) { int&x=Dp[i][a1][a2];x=-inf; if(a1) { Renew(x,Dp[i][a1-1][a2]); for(int o=0;o<a1;o++) Renew(x,Dp[i-1][o][a2]+A[0][a1]-A[0][o]); } if(a2) { Renew(x,Dp[i][a1][a2-1]); for(int o=0;o<a2;o++) Renew(x,Dp[i-1][a1][o]+A[1][a2]-A[1][o]); } if(a1==a2) { for(int o=0;o<a1;o++) Renew(x,Dp[i-1][o][o]+S[a1]-S[o]); } } cout<<Dp[k][n][n]<<endl;}int main(){ //freopen("in","r",stdin); cin>>n>>m>>k; if(m==1)Solve1(); else Solve2();}93 2 21 -32 3-2 3