Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:xxxxxxxxxxxxxxx

Posted by hookun at 2008-09-27 18:01:30 on Problem 1112
In Reply To:xxxxxxxxxxxxxxx Posted by:zhangxiao1124 at 2008-05-05 20:39:19
great ,赞!
> /*
>   先求补图Init(),再黑白染色Calc(),然后Dp(),最后Print()
> */
> #include<iostream>
> using namespace std;
> #define maxn 105
> #define Inf 1000000
> int n,m,v[maxn],s[maxn][2],f[maxn][maxn],p[maxn][maxn];
> bool g[maxn][maxn];
> 
> void Init() {
>     scanf("%d",&n);
>     for (int i=1; i<=n; i++) {
>         int j;
>         while (scanf("%d",&j),j) g[i][j]=true;
>     }
>     for (int i=1; i<=n-1; i++)
>         for (int j=i+1; j<=n; j++)
>             g[i][j]=g[j][i]=!(g[i][j] && g[j][i]);
> }
> 
> bool Dye(int i,int flag) {
>     v[i]=(flag)?-m:m,s[m][flag]++;
>     for (int j=1; j<=n; j++) if (g[i][j])
>         if (v[i]==v[j] || !v[j] && !Dye(j,flag^1)) return false;
>     return true;
> }
> 
> bool Calc() {
>     for (int i=1; i<=n; i++) if (!v[i]) {
>         m++;
>         if (!Dye(i,0)) return false;
>     }
>     return true;
> }
> 
> void Dp() {
>     fill_n(f[0],maxn*maxn,-Inf);
>     for (int j=0; j<=n/2; j++) f[0][j]=0;
>     for (int i=1; i<=m; i++)
>         for (int j=1; j<=n/2; j++)
>             if (s[i][1]) {
>                 if (j>=s[i][0]) f[i][j]=f[i-1][j-s[i][0]]+s[i][0];
>                 if (j>=s[i][1] && f[i-1][j-s[i][1]]+s[i][1]>f[i][j]) {
>                     f[i][j]=f[i-1][j-s[i][1]]+s[i][1];
>                     p[i][j]=1;
>                 }
>             } else {
>                 f[i][j]=f[i-1][j],p[i][j]=-1;
>                 if (j>=s[i][0] && f[i-1][j-s[i][0]]+s[i][0]>f[i][j]) {
>                     f[i][j]=f[i-1][j-s[i][0]]+s[i][0];
>                     p[i][j]=0;
>                 }
>             }
> }
> 
> bool ans[maxn];
> int rec[maxn];
> void Print() {
>     int limit=n/2,now=m;
>     while (now>0) {
>         rec[now]=p[now][limit];                         //一开始打成p[limit][now] , 郁闷了好半天
>         if (rec[now]>-1) limit-=s[now][rec[now]];
>         now--;
>     }
>     for (int i=1; i<=n; i++)
>         if (v[i]>0 && rec[v[i]]==0) ans[i]=true;
>         else if (v[i]<0 && rec[-v[i]]==1) ans[i]=true;
>     printf("%d",f[m][n/2]);
>     for (int i=1; i<=n; i++) if (ans[i]) printf(" %d",i); printf("\n");
>     printf("%d",n-f[m][n/2]);
>     for (int i=1; i<=n; i++) if (!ans[i]) printf(" %d",i); printf("\n");
> }
> 
> int main() {
>     Init();
>     if (!Calc()) {
>         puts("No solution");
>         return 0;
>     }
>     Dp();
>     Print();
>     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator