200 Rare Order poao899 Accepted C++ 0.012 2009-12-12 11:28:09 .
不難不過覺得好有趣(?
寫過太多奇怪的算法好久沒有好好想一題了雖然這是我的問題XD
算是...最短路...吧
找出相鄰兩列可以知道的大小關係
再去建圖
//*********************
//UVa 200
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 100000
struct alpha{
int cha,rank,in,out;
bool operator<(const alpha &b)const{
return rank<b.rank;
}
}A[30];
int dist[30][30],nlen,plen,st,cnt;
char S1[30],S2[30];
main(){
char *now=S1,*pre=S2,*t;
//Initialize
for(int i=0;i<30;i++){
A[i].cha='A'+i;
for(int j=0;j<30;j++)
dist[i][j]=INF;
}
//Input
while(1){
gets(now);
if(now[0]=='#')break;
nlen=strlen(now);
for(int i=0;i<nlen&&i<plen;i++)
if(now[i]!=pre[i]){
dist[pre[i]-'A'][now[i]-'A']=-1;
A[now[i]-'A'].in++;
A[pre[i]-'A'].out++;
break;
}
plen=nlen;
t=now;now=pre;pre=t;
}
//Find Start
for(int i=0;i<30;i++){
if(A[i].in+A[i].out >0 && A[i].in==0){
st=i;
break;
}
}
dist[st][st]=0;
//Floyd-Warshall
for(int k=0;k<30;k++)
for(int i=0;i<30;i++)
for(int j=0;j<30;j++)
if(dist[i][k]+dist[k][j] < dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
//Rank
for(int i=0;i<30;i++){
if(dist[st][i]<=0)
A[i].rank=-dist[st][i];
else A[i].rank=10000;
}
//Sort
std::sort(A,A+30);
//Output
for(int i=0;i<30;i++){
if(A[i].rank==10000)break;
printf("%c",A[i].cha);
}
printf("\n");
}
2009年12月12日 星期六
2009年12月11日 星期五
UVa 11045 My T-shirt suits me [Flow]
11045 My T-shirt suit... poao899 Accepted C++ 0.020 2009-12-12 05:59:59 .
花了半小時co
不過少打一個括號debug半小時= =
是說 同TIOJ 1469 制服發放問題
不過貌似有其他解法= =看TIOJ大家的速度...還有code length
應該是有辦法greedy?
//******************************
//13:04 - 13:31
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define INF 100000
struct arc{
int j,con;
arc *topair,*next;
void set(int to,int c,arc *t,arc *n){
j=to;con=c;
topair=t;next=n;
}
}A[MAX],*N[MAX],*from[MAX];
int arr[INF],t;
struct queue{
int front,rear,*ar;
void init(){
front=rear=0;
ar=arr;
}
int deq(){
int a=ar[front];
front=++front%INF;
return a;
}
void enq(int a){
ar[rear]=a;
rear=++rear%INF;
}
}q;
int arcCnt,n,m,max,fa[MAX];
char s[10];
arc* get(){
return A+arcCnt++;
}
void build(int i,int j,int c){
arc *p=get(),*q=get(),*r;
r=N[i];
N[i]=p;
p->set(j,c,q,r);
r=N[j];
N[j]=q;
q->set(i,0,p,r);
}
/*
S 0
T MAX-1
size
XXL - XS 201 - 206
*/
main(){
scanf("%d",&t);
while(t--){
scanf("%d%d\n",&n,&m);
//Initialize
arcCnt=max=0;
for(int i=0;i<MAX;i++){
A[i].topair=A[i].next=N[i]=NULL;
}
// S & T
n/=6;
for(int i=201;i<207;i++)
build(0,i,n);
//Input
for(int i=1;i<=m;i++){
int toSet;
for(int j=0;j<2;j++){
scanf("%s",s);
if(s[0]=='X'){
if(s[1]=='X')
toSet=201;
else if(s[1]=='L')
toSet=202;
else if(s[1]=='S')
toSet=206;
}
else{
switch(s[0]){
case'L':
toSet=203;
break;
case'M':
toSet=204;
break;
case'S':
toSet=205;
break;
}
}
build(toSet,i,1);
}
build(i,999,1);
}
//Max-Flow
while(1){
int flow=INF;
//Initialize
for(int i=0;i<MAX;i++){
fa[i]=-1;
from[i]=NULL;
}
q.init();
q.enq(0);
//BFS
while(q.front!=q.rear){
int now=q.deq();
for(arc *p=N[now];p;p=p->next){
if(p->con > 0 && fa[p->j]==-1){
q.enq(p->j);
fa[p->j]=now;
from[p->j]=p;
}
}
}
if(fa[999]==-1)break;
//flow
for(int now=999;now;now=fa[now]){
if(flow>from[now]->con)
flow=from[now]->con;
}
if(!flow)break;
for(int now=999;now;now=fa[now]){
from[now]->con-=flow;
from[now]->topair->con+=flow;
}
max+=flow;
}
puts(max==m?"YES":"NO");
}
}
花了半小時co
不過少打一個括號debug半小時= =
是說 同TIOJ 1469 制服發放問題
不過貌似有其他解法= =看TIOJ大家的速度...還有code length
應該是有辦法greedy?
//******************************
//13:04 - 13:31
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define INF 100000
struct arc{
int j,con;
arc *topair,*next;
void set(int to,int c,arc *t,arc *n){
j=to;con=c;
topair=t;next=n;
}
}A[MAX],*N[MAX],*from[MAX];
int arr[INF],t;
struct queue{
int front,rear,*ar;
void init(){
front=rear=0;
ar=arr;
}
int deq(){
int a=ar[front];
front=++front%INF;
return a;
}
void enq(int a){
ar[rear]=a;
rear=++rear%INF;
}
}q;
int arcCnt,n,m,max,fa[MAX];
char s[10];
arc* get(){
return A+arcCnt++;
}
void build(int i,int j,int c){
arc *p=get(),*q=get(),*r;
r=N[i];
N[i]=p;
p->set(j,c,q,r);
r=N[j];
N[j]=q;
q->set(i,0,p,r);
}
/*
S 0
T MAX-1
size
XXL - XS 201 - 206
*/
main(){
scanf("%d",&t);
while(t--){
scanf("%d%d\n",&n,&m);
//Initialize
arcCnt=max=0;
for(int i=0;i<MAX;i++){
A[i].topair=A[i].next=N[i]=NULL;
}
// S & T
n/=6;
for(int i=201;i<207;i++)
build(0,i,n);
//Input
for(int i=1;i<=m;i++){
int toSet;
for(int j=0;j<2;j++){
scanf("%s",s);
if(s[0]=='X'){
if(s[1]=='X')
toSet=201;
else if(s[1]=='L')
toSet=202;
else if(s[1]=='S')
toSet=206;
}
else{
switch(s[0]){
case'L':
toSet=203;
break;
case'M':
toSet=204;
break;
case'S':
toSet=205;
break;
}
}
build(toSet,i,1);
}
build(i,999,1);
}
//Max-Flow
while(1){
int flow=INF;
//Initialize
for(int i=0;i<MAX;i++){
fa[i]=-1;
from[i]=NULL;
}
q.init();
q.enq(0);
//BFS
while(q.front!=q.rear){
int now=q.deq();
for(arc *p=N[now];p;p=p->next){
if(p->con > 0 && fa[p->j]==-1){
q.enq(p->j);
fa[p->j]=now;
from[p->j]=p;
}
}
}
if(fa[999]==-1)break;
//flow
for(int now=999;now;now=fa[now]){
if(flow>from[now]->con)
flow=from[now]->con;
}
if(!flow)break;
for(int now=999;now;now=fa[now]){
from[now]->con-=flow;
from[now]->topair->con+=flow;
}
max+=flow;
}
puts(max==m?"YES":"NO");
}
}
UVa 567 Risk [Shortest Path]
567 Risk poao899 Accepted C++ 0.084 2009-12-11 15:33:06 .
昨天看題目看了十幾分鐘竟然是無腦題=口=
20個點沒有權重的最短路orz
//********************************
#include<stdio.h>
#define INF 1000000
int dist[30][30],cnt,a,b,n;
main(){
for(int z=1;~scanf("%d",&cnt);z++){
printf("Test Set #%d\n",z);
for(int i=0;i<30;i++)
for(int j=0;j<30;j++)
dist[i][j]=i==j?0:INF;
for(int i=1;i<20;i++){
while(cnt-->0){
scanf("%d",&n);
dist[i][n]=dist[n][i]=1;
}
scanf("%d",&cnt);
}
//Floyd –Warshall
for(int k=1;k<=20;k++)
for(int i=1;i<=20;i++)
for(int j=1;j<=20;j++)
if(dist[i][k]+dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k]+dist[k][j];
for(int i=0;i<cnt;i++){
scanf("%d%d",&a,&b);
printf("%2d to %2d:%2d\n",a,b,dist[a][b]);
}
puts("");
}
}
昨天看題目看了十幾分鐘竟然是無腦題=口=
20個點沒有權重的最短路orz
//********************************
#include<stdio.h>
#define INF 1000000
int dist[30][30],cnt,a,b,n;
main(){
for(int z=1;~scanf("%d",&cnt);z++){
printf("Test Set #%d\n",z);
for(int i=0;i<30;i++)
for(int j=0;j<30;j++)
dist[i][j]=i==j?0:INF;
for(int i=1;i<20;i++){
while(cnt-->0){
scanf("%d",&n);
dist[i][n]=dist[n][i]=1;
}
scanf("%d",&cnt);
}
//Floyd –Warshall
for(int k=1;k<=20;k++)
for(int i=1;i<=20;i++)
for(int j=1;j<=20;j++)
if(dist[i][k]+dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k]+dist[k][j];
for(int i=0;i<cnt;i++){
scanf("%d%d",&a,&b);
printf("%2d to %2d:%2d\n",a,b,dist[a][b]);
}
puts("");
}
}
TIOJ 1174 The Shortest Distance
nolonger 896K 478MS G++ 0.29K 2009-12-11 16:03:17 .
唔很像Mearge Sort的作法...
排序後O(n)
//************************
唔很像Mearge Sort的作法...
排序後O(n)
//************************
#include<algo.h>
int a[200000],b[200000],n,m,z;
main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",a+i);
for(int i=0;i<m;i++)
scanf("%d",b+i);
sort(a,a+n);
sort(b,b+m);
z=1<<31-1;
for(int i=0,j=0;i<n&&j<m;a[i]>b[j]?j++:i++)
z<?=abs(a[i]-b[j]);
printf("%d\n",z);
}
TIOJ 1061 井字遊戲(TTT) [ 95北市賽 ] [DFS]
poao899 0K 167MS G++ 0.84K 2009-12-11 15:29:25 .
DFS + Hash判重(咦好像不是這樣用
是說co了四次QQ
有兩次在DFS時不printf()會跑不起來超詭異
//*****************************
#include<stdio.h>
short way[8][3]={
0,1,2,
3,4,5,
6,7,8,
0,3,6,
1,4,7,
2,5,8,
0,4,8,
2,4,6,
};
short n,st,cnt[3],a[10],o,x,c;
bool H[19683];
bool hash(){
int h=0;
for(int i=0;i<9;i++)
h=h*3+a[i];
if(H[h])return 1;
H[h]=1;return 0;
}
int chk(){
short x;
for(int i=0;i<8;i++)
if((x=a[way[i][0]]) == a[way[i][1]] && a[way[i][1]] == a[way[i][2]] && x)
return x;
return 0;
}
void dfs(bool pl){
int b=0,x=chk();
if(x){
if(!hash())
cnt[x]++;
return;
}
for(int i=0;i<9;i++){
if(a[i]==0){
a[i]=pl+1;
dfs(!pl);
a[i]=0;
b=1;
}
}
if(!b && !hash())
cnt[x]++;
}
main(){
for(int z=0;z<9;z++){
c=getchar();
if(c=='O'){o++;a[z]=1;}
else if(c=='X'){x++;a[z]=2;}
else a[z]=0;
}
dfs(o>x);
printf("%hd %hd %hd %hd\n",cnt[0]+cnt[1]+cnt[2],cnt[1],cnt[2],cnt[0]);
}
DFS + Hash判重(咦好像不是這樣用
是說co了四次QQ
有兩次在DFS時不printf()會跑不起來超詭異
//*****************************
#include<stdio.h>
short way[8][3]={
0,1,2,
3,4,5,
6,7,8,
0,3,6,
1,4,7,
2,5,8,
0,4,8,
2,4,6,
};
short n,st,cnt[3],a[10],o,x,c;
bool H[19683];
bool hash(){
int h=0;
for(int i=0;i<9;i++)
h=h*3+a[i];
if(H[h])return 1;
H[h]=1;return 0;
}
int chk(){
short x;
for(int i=0;i<8;i++)
if((x=a[way[i][0]]) == a[way[i][1]] && a[way[i][1]] == a[way[i][2]] && x)
return x;
return 0;
}
void dfs(bool pl){
int b=0,x=chk();
if(x){
if(!hash())
cnt[x]++;
return;
}
for(int i=0;i<9;i++){
if(a[i]==0){
a[i]=pl+1;
dfs(!pl);
a[i]=0;
b=1;
}
}
if(!b && !hash())
cnt[x]++;
}
main(){
for(int z=0;z<9;z++){
c=getchar();
if(c=='O'){o++;a[z]=1;}
else if(c=='X'){x++;a[z]=2;}
else a[z]=0;
}
dfs(o>x);
printf("%hd %hd %hd %hd\n",cnt[0]+cnt[1]+cnt[2],cnt[1],cnt[2],cnt[0]);
}
TIOJ 1042 E.老問題 [ NPSC2003初賽 ] [Flow]
poao899 716K 140MS G++ 1.94K 2009-12-11 11:59:34 .
Minimum-Cost Maximum Flow.
第一題最小花費最大流>//<
是說相鄰矩陣比相鄰串列好寫多了
一開始WA得莫名重co一次就過了= =
//**************************
#include<stdio.h>
#define MAX 2147483647
#define NODE 300
#define QLEN 1000000
int con[NODE][NODE],cost[NODE][NODE],dist[NODE],from[NODE];
bool inq[NODE];
int arr[QLEN];
struct queue{
int front,rear,*ar;
void init(){
front=rear=0;
ar=arr;
}
int deq(){
int x=ar[front];
front=++front%QLEN;
return x;
}
void enq(int a){
ar[rear]=a;
rear=++rear%QLEN;
}
}q;
int n,t,max;
main(){
while(scanf("%d",&n),n){
//Initialize
max=0;
for(int i=0;i<NODE;i++)
for(int j=0;j<NODE;j++)
con[i][j]=cost[i][j]=0;
for(int i=1;i<=n;i++)
con[0][i]=con[i+150][NODE-1]=1;
//Input
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&t);
con[i][j+150]=1;
cost[i][j+150]=-t;
cost[j+150][i]=t;
if(!t)con[i][j+150]=1;
}
while(1){
//Initialize
q.init();q.enq(0);
int flow=MAX,now,m=0;
for(int i=0;i<NODE;i++){
dist[i]=MAX;inq[i]=0;
from[i]=-1;
}
//SPFA
dist[0]=0;inq[0]=1;
while(q.front!=q.rear){
now=q.deq();
for(int i=0;i<=NODE;i++){
if(con[now][i]>0 && dist[i]>dist[now]+cost[now][i]){
dist[i]=dist[now]+cost[now][i];
from[i]=now;
if(!inq[i]){
inq[i]=1;
q.enq(i);
}
}
}
inq[now]=0;
}
if(from[NODE-1] == -1)break;
for(now=NODE-1;now;now=from[now]){
if(flow>con[from[now]][now])
flow=con[from[now]][now];
}
for(now=NODE-1;now;now=from[now]){
m+=cost[from[now]][now];
con[from[now]][now]-=flow;
con[now][from[now]]+=flow;
}
if(m<=0)
max+=m;
}
printf("%d\n",-max);
}
}
Minimum-Cost Maximum Flow.
第一題最小花費最大流>//<
是說相鄰矩陣比相鄰串列好寫多了
一開始WA得莫名重co一次就過了= =
//**************************
#include<stdio.h>
#define MAX 2147483647
#define NODE 300
#define QLEN 1000000
int con[NODE][NODE],cost[NODE][NODE],dist[NODE],from[NODE];
bool inq[NODE];
int arr[QLEN];
struct queue{
int front,rear,*ar;
void init(){
front=rear=0;
ar=arr;
}
int deq(){
int x=ar[front];
front=++front%QLEN;
return x;
}
void enq(int a){
ar[rear]=a;
rear=++rear%QLEN;
}
}q;
int n,t,max;
main(){
while(scanf("%d",&n),n){
//Initialize
max=0;
for(int i=0;i<NODE;i++)
for(int j=0;j<NODE;j++)
con[i][j]=cost[i][j]=0;
for(int i=1;i<=n;i++)
con[0][i]=con[i+150][NODE-1]=1;
//Input
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&t);
con[i][j+150]=1;
cost[i][j+150]=-t;
cost[j+150][i]=t;
if(!t)con[i][j+150]=1;
}
while(1){
//Initialize
q.init();q.enq(0);
int flow=MAX,now,m=0;
for(int i=0;i<NODE;i++){
dist[i]=MAX;inq[i]=0;
from[i]=-1;
}
//SPFA
dist[0]=0;inq[0]=1;
while(q.front!=q.rear){
now=q.deq();
for(int i=0;i<=NODE;i++){
if(con[now][i]>0 && dist[i]>dist[now]+cost[now][i]){
dist[i]=dist[now]+cost[now][i];
from[i]=now;
if(!inq[i]){
inq[i]=1;
q.enq(i);
}
}
}
inq[now]=0;
}
if(from[NODE-1] == -1)break;
for(now=NODE-1;now;now=from[now]){
if(flow>con[from[now]][now])
flow=con[from[now]][now];
}
for(now=NODE-1;now;now=from[now]){
m+=cost[from[now]][now];
con[from[now]][now]-=flow;
con[now][from[now]]+=flow;
}
if(m<=0)
max+=m;
}
printf("%d\n",-max);
}
}
2009年12月10日 星期四
TIOJ 1236 工廠生產問題 [ TOI 2006 ] [Flow]
poao899 184K 289MS G++ 1.62K 2009-12-10 16:13:52 .
一樣是Flow =w=
唔MAX一開始調10^9會WA
哪家工廠生產這麼有效率啦(翻桌
是說這題要拆點、沒給測資範圍
然後就沒什麼特別了(?
//****************************
一樣是Flow =w=
唔MAX一開始調10^9會WA
哪家工廠生產這麼有效率啦(翻桌
是說這題要拆點、沒給測資範圍
然後就沒什麼特別了(?
//****************************
#include<stdio.h>
#define QLEN 1000100
#define MAX 2147483647
#define NMAX 1000
struct arc{
int j,con;
arc *next,*topair;
void set(int to,int c,arc* n,arc* t){
j=to;con=c;
next=n;topair=t;
}
}A[1000000],*N[NMAX],*from[NMAX];
int que[QLEN];
struct queue{
int front,rear;
int *ar;
void init(){
ar=que;
front=rear=0;
}
void enq(int a){
ar[rear]=a;
rear=++rear%QLEN;
}
int deq(){
int x=ar[front];
front=++front%QLEN;
return x;
}
}q;
arc* get(){
static int cnt=0;
return A+cnt++;
}
void build(int i,int j,int con){
arc *p=get(),*q=get(),*r;
r=N[i];
N[i]=p;
p->set(j,con,r,q);
r=N[j];
N[j]=q;
q->set(i,0,r,p);
}
int n,m,a,b,f,max,indeg[NMAX],outdeg[NMAX],fa[NMAX],c;
int bfs(){
for(int i=0;i<NMAX;i++)
fa[i]=-1;
q.init();
q.enq(0);
int flow=MAX;
while(q.front!=q.rear){
int now=q.deq();
for(arc *p=N[now];p;p=p->next){
if(fa[p->j]==-1 && p->con > 0){
q.enq(p->j);
fa[p->j]=now;
from[p->j]=p;
if(flow > p->con)
flow=p->con;
}
}
}
if(fa[999]==-1)return 0;
return flow;
}
void resi(int flow){
for(int now=999;now;now=fa[now]){
from[now]->con-=flow;
from[now]->topair->con+=flow;
}
}
main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&c);
build(i,i+500,c);
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
build(a+500,b,MAX);
indeg[b]++;
outdeg[a]++;
}
for(int i=1;i<=n;i++){
if(!indeg[i])
build(0,i,MAX);
if(!outdeg[i])
build(i+500,999,MAX);
}
while(1){
f=bfs();
if(!f)break;
resi(f);
max+=f;
}
printf("%d\n",max);
}
訂閱:
文章 (Atom)