# 2012年11月10日

KMP

TimeLimit: 1 Second   MemoryLimit: 32 Megabyte

Totalsubmit: 2   Accepted: 1

Description

Input

Output

Sample Input

zhonghongyihelafeng
5
zhonghongyihenshuai 10
zhonghongyihennx 10
zhonghongyihenyingjun 10
wobuxihuanheichuxing 10
bbaze
3
bzb 2
aeb 3
ba 10

Sample Output

-1
8

Source

zhy

#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 1010
#define MAXM 1000200
#define INF (1<<29)
int sumFlow;
struct Edge{
int u,v,cap,cost;
int next;
}edge[MAXM<<2];
int NE;
bool vis[MAXN];
char ch[MAXN] ;
int k , n;
void init(){
NE = 0;
}
void addedge(int u,int v,int cap,int cost){
edge[NE].u=u;edge[NE].v=v;edge[NE].cap=cap;edge[NE].cost=cost;
edge[NE].u=v;edge[NE].v=u;edge[NE].cap=0;edge[NE].cost=-cost;
}
bool SPFA(int s,int t,int n){
int i,u,v;
queue<int> qu;
memset(vis,0,sizeof(vis));
memset(pp,-1,sizeof(pp));
for(i=0;i<=n;i++) dist[i]=INF;
vis[s]=1;dist[s]=0;
qu.push(s);
while(!qu.empty()){
u=qu.front();qu.pop();vis[u]=0;
v=edge[i].v;
if(edge[i].cap && dist[v]>dist[u]+edge[i].cost){
dist[v]=dist[u]+edge[i].cost;
pp[v]=i;
if(!vis[v]){
qu.push(v);
vis[v]=true;
}
}
}
}
if(dist[t]==INF) return false;
return true;
}
int MCMF(int s,int t,int n){//最小费用最大流
int flow = 0;    //总流量
int i,minflow,mincost;
mincost = 0;
while(SPFA(s,t,n)){
minflow = INF+1;
for(i=pp[t];i!=-1;i=pp[edge[i].u])
if(edge[i].cap<minflow)
minflow = edge[i].cap;
flow+=minflow;
for(i=pp[t];i!=-1;i=pp[edge[i].u]){
edge[i].cap-=minflow;
edge[i^1].cap+=minflow;
}
mincost += dist[t]*minflow;
}
sumFlow = flow;//最大流
return mincost;
}
int C[33] , cnt[33] , a[111];
int main() {
while(~scanf("%s",ch)) {
int L = strlen(ch);
memset(C,0,sizeof(C));
for(int i=0;i<L;i++) {
int aa = ch[i] - 'a';
C[aa] ++;
}
scanf("%d",&k);
n = 27 * k + 30;
int s = 27 * k + 28 , t = 27 * k + 29;
init();
for(int i=1;i<=k;i++) {
for(int j=0;j<26;j++) {
}
scanf("%s",ch);
scanf("%d",&a[i]);
int len = strlen(ch);
memset(cnt,0,sizeof(cnt));
for(int j=0;j<len;j++) {
int aa = ch[j] - 'a';
cnt[aa] ++;
}
for(int j=0;j<26;j++) {
if(cnt[j]) {
}
//printf("a[i] is %d\n",a[i]);
}
}
int ans = MCMF(s,t,n);
if(sumFlow == L) printf("%d\n",ans);
else printf("-1\n");
//printf("default : sumFlow is %d , mincost is %d \n",sumFlow,ans);
}
return 0;
}

TimeLimit: 1 Second   MemoryLimit: 32 Megabyte

Totalsubmit: 20   Accepted: 4

Description

Input

Output

Sample Input

1
4 1

Sample Output

3

Source

lrl

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[1010][1010];
int sum[1010][1010];
int n , k , T;
int S(int nn , int kk) {
if(kk<0) return 0;
else return sum[nn][kk] % 10000;
}
void init() {
for(int i=1;i<=1000;i++) f[i][0] = sum[i][0] = 1;
for(int i=1;i<=1000;i++)
for(int j=1;j<=1000;j++) {
f[i][j] = (S(i-1,j) - S(i-1,j-i)) % 10000;
while(f[i][j] < 0) f[i][j] += 10000;
sum[i][j] = ( sum[i][j-1] + f[i][j] ) % 10000;
}
}
int main() {
init();
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&k);
printf("%d\n",f[n][k]);
}
return 0;
}

posted @ 2012-11-10 21:44 lenohoo 阅读(138) | 评论 (0)编辑 收藏

# 2012年10月15日

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000;
int p[maxn];
int b[505][505];
int n;
void init() {
for(int i=0;i<(2*n+1)*32+100;i++) p[i] = i;
}
int find(int x) {
return x==p[x] ? x : p[x] = find(p[x]);
}
void Union(int x,int y) {
int a = find(x) , b = find(y);
p[a] = p[b] = p[x] = p[y] = min(a , b);
}
bool check() {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++)
if(b[i][j] != b[j][i]) return 0;
if(b[i][i] != 0) return 0;
}
init();
int m = 32 * n;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) {
if(i % 2 == 0 && j % 2 == 0) {
for(int k=0;k<32;k++) {
if(b[i][j] & (1<<k) == 0) {
int u = i*32+k , v = j*32+k;
if(find(u) == find(1) || find(v) == find(1) || find(u) == find(v+m)) return 0;
Union(u,0);
Union(v,0);
Union(u+m,1);
Union(v+m,1);
}
}
}
else if(i % 2 == 1 && j % 2 == 1) {
for(int k=0;k<32;k++) {
if(b[i][j] & (1<<k)) {
int u = i* 32 + k , v = j*32+k;
if(find(u) == find(0) || find(v)==find(0) || find(u) == find(v+m)) return 0;
Union(u,1);
Union(v,1);
Union(u+m,0);
Union(v+m,0);
}
}
}
else {
for(int k=0;k<32;k++) {
int u = i * 32 + k , v = j * 32 + k;
if(b[i][j] & (1<<k)) {
if(find(u) == find(v)) return 0;
Union(u,v+m);
Union(u+m,v);
}
else {
if(find(u) == find(v+m)) return 0;
Union(u,v);
Union(u+m,v+m);
}
}
}
}
return 1;
}
int main() {
while(~scanf("%d",&n)) {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&b[i][j]);
if(check()) puts("YES");
else puts("NO");
}
return 0;
}

posted @ 2012-10-15 21:04 lenohoo 阅读(134) | 评论 (0)编辑 收藏

# 2012年5月17日

b - a < = c     <==>    add_edge(a - > b , c)

posted @ 2012-05-17 11:52 lenohoo 阅读(140) | 评论 (0)编辑 收藏

posts - 3, comments - 1, trackbacks - 0, articles - 16