#include <iostream>
using namespace std;
int f[60005];
#define MAX(a,b) a>b?a:b
void Complete(int cost, int weight, int m)
{
for(int i = cost; i <= m; i++)
f[i] = MAX(f[i], f[i - cost] + weight);
}
void Zero_One(int cost, int weight, int m)
{
for(int i = m; i >= cost; i--)
f[i] = MAX(f[i], f[i - cost] + weight);
}
int main(int argc, char *argv[])
{
int a[7],n,i,j,sum,t=0;
while(1)
{
sum=0;
for(i=1;i<7;i++)
{
scanf("%d",a+i);
sum+=a[i]*i;
}
if(!sum) break;
if(sum&1)
{ printf("Collection #%d:\n",++t);
puts("Can't be divided.\n");
continue;
}
sum >>= 1;
memset(f,0,sizeof(f));
for(i=1;i<7;i++)
{
if(a[i]*i>=sum)
{
Complete(i,i,sum);
}
else if(a[i]>0)
{
int k=1;
while(k<a[i])
{
Zero_One(k*i,k*i,sum) ;
a[i]-=k;
k <<= 1;
}
for(j=sum;j>=i*a[i];j--)
{
Zero_One(a[i]*i,a[i]*i,sum);
}
}
}
if(f[sum]==sum)
{
printf("Collection #%d:\n",++t);
puts("Can be divided.\n");
}
else
{printf("Collection #%d:\n",++t);
puts("Can't be divided.\n");
}
}
// system("PAUSE");
return EXIT_SUCCESS;
}
//榪欐槸鎴戠殑浠ｇ爜涓轟粈涔堟繪槸瓚呮椂鍛紵姹傝В閲娿傘?img src ="http://www.shnenglu.com/syhd142/aggbug/152303.html" width = "1" height = "1" />
songzhongping 2011-08-02 18:57 鍙戣〃璇勮
]]>#include <math.h>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
#define kind 129
#define M 10010
struct node {
node *fail;
node *next[kind];
int id;
node() { //鏋勯犲嚱鏁?
fail = NULL;
id = 0;
memset(next, NULL, sizeof(next));
}
};
char ch[M]; //閿洏杈撳叆鐨勪覆
queue<node *> q;
set <int> g;
int n, m;
void insert(node *root, char *str, int num) {
node *p = root;
int i = 0, index;
while(str[i]) {
index = str[i] - 'a';
if(p->next[index] == NULL) {
p->next[index] = new node();
}
p = p->next[index];
i++;
}
p->id = num;
}
void AC (node *&root) { ///root -> fail = NULL;
q.push(root);
while(!q.empty()) {
node *p = NULL;
node *t = q.front();
q.pop();
for(int i = 0; i < kind; i++) {
if(t->next[i]) {
p = t->fail;
while(p) {
if(p->next[i]) {
t->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(!p) t->next[i]->fail = NULL;
q.push(t->next[i]);
}
}
}
}
bool query(node *&root, char *str, int ca) {
g.clear();
int i = 0, t, flag = 0;
node *p = root, *tmp;
while(str[i]) {
t = str[i] - 'a';
while(!p->next[t] && p != root) { p = p->fail; }
///*****************************///
p = p->next[t];
///******************************///
if(!p) p = root;
tmp = p;
while(tmp != root && tmp->id) {
flag = 1;
g.insert(tmp->id);
tmp = tmp->fail;
}
i++;
}
if(!flag) return false;
printf("web %d:", ca);
for(set<int>::iterator it = g.begin(); it != g.end(); it++) {
cout << ' ' << *it;
}
cout << endl;
return true;
}
int main() {
int total;
while(~scanf("%d", &n)) {
node *root = new node();
total = 0;
for(int i = 0; i < n; i++) {
scanf("%s", ch);
insert(root, ch, i+1);
}
AC(root);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> ch;
if(query(root, ch, i+1)); total++;
}
printf("total: %d\n", total);
}
return 0;
}
甯繖鐪嬬湅鍚э紒妤間富錛岀収浣犵殑鍐欑殑錛屼絾鏄繕鏄笉琛岋紝杈撳叆閮戒笉琛?img src ="http://www.shnenglu.com/syhd142/aggbug/146361.html" width = "1" height = "1" />
]]>
]]>
榪欑粍鎴戠敤浣犵殑紼嬪簭璁＄畻鍑烘潵鐨勬槸43 2 sum:45.
搴旇鏄? 10 12 9 8 2 sum:45
涓轟粈涔堝彲浠ヨ繖鏍瘋褰曡礬寰勶紵
]]>
Very Simple Methods for All Pairs Network Flow Analysis
caocao9926@163.com
]]>
濡備綍鍦ㄦ眰minimum cost鍊肩殑鍚屾椂錛?
璁板綍鎵cut鐨勭偣鐨勬搴??琚洶鎵板ソ涔呫傘傘傘傘?
姣斿input:
10 (鏈ㄦ闀?
3 錛堝垏3嬈★級
2 4 7 錛堝湪2錛?錛?澶勫垏錛?
Output:
The minimum cost is 20.
The optimal cutting sequence: 4,2,7
jerrymu1234 2010-11-17 14:01 鍙戣〃璇勮
]]>]]>