这么想的 源点和1-7天之间容量无限大 ，1-7天和week之间要么为0要么为1  week和 task之间 有关联的容量无限大 task和汇点之间容量为 已知天数  最后最大流等于总需要天数时 返回yes 
最多有 7+ 50 +20 +2 =79个点不算很大。。。可还是不对 
代码： 

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define inf (1<<30)
typedef struct Node{
       int prenum;
       int token;
       int con;
}node;
typedef node* mnode;
mnode newnode(){
     mnode m=new node();
     m->prenum=0;
     m->token=0;
     m->con=0;               //瀹归噺 
     return m;
}
mnode v[100]; 



int mc[100][100];
int ma[100][100];
int week[8];
int check[100];
int main(){
    const int totaltask = 20;
    const int totalweek = 50;
	int n;cin>>n;
	int work,numofweek,flow,sum;
	for(int i=0;i<100;i++){
       v[i]=newnode();     
    }
	while(n--){
        sum=0;
		memset(mc,0,sizeof(mc));
		memset(ma,0,sizeof(ma));
		memset(check,0,sizeof(check));
		cin>>work;
		for(int i=1;i<=work;i++){
			for(int j=1;j<=7;j++){
				cin>>week[j];
			}
			cin>>flow>>numofweek;
			sum+=flow;
			for(int j=1;j<=7;j++){
				mc[0][j]=inf;
			}
			for(int j=1;j<=numofweek;j++){
				for(int k=1;k<=7;k++){
					if(week[k]) {
						mc[k][7+j]=1;
					} 
				}
				mc[7+j][7+totalweek+i]=inf;
			}
			mc[7+totalweek+i][7+totalweek+work+1]=flow;			
		}
		/*for(int i=0;i<=8+totalweek+work;i++){
			for(int j=0;j<=8+totalweek+work;j++){
				cout<<mc[i][j]<<"  ";
			}
			cout<<endl;
		}
		*/
		int dest=8+totalweek+work;
		
		
		
		
		
		queue< int> q;
   		 //浠?寮€濮?
   		 bool flag=true;
   		 while(flag){
			memset(check,0,sizeof(check));
			for(int i=0;i<=dest;i++){
				v[i]->prenum=-1;
				v[i]->token=0;
				v[i]->con=0;
			}
			while(!q.empty()) q.pop();
    		v[0]->con=0;
   			v[0]->con=inf;
   			check[0]=1;
			q.push(0);
			while(check[dest]==0){               //n鐐规爣璁颁簡 杩樻病妫€鏌?
				bool allcheck=true;
				for(int k=0;k<=dest;k++){
					if(check[k]==1) {allcheck=false;break;}
				}
				if(allcheck){
					int count=0;                    //浠€涔堟椂鍊欐墠浼氳繘鍏ヨ繖閲屽憿 锛屽彧鏈夊綋鎵句笉鍒板骞胯矾鐨勬椂鍊?
					for(int k=0;k<=dest;k++){
						count+=ma[k][dest];
					}
					if(count==sum) cout<<"YES"<<endl;
					else cout<<"NO"<<endl;
					flag=false;
					break;
				}
				
					int inum=q.front();
					q.pop();
					for(int i=0;i<=dest;i++){
						if(i==inum) continue;
						if(ma[inum][i]<mc[inum][i]&&check[i]==0){
							check[i]=1;
							q.push(i);
							v[i]->prenum=inum;
							v[i]->con=min(v[inum]->con,mc[inum][i]-ma[inum][i]);
						}
						else if(ma[i][inum]>0&&check[i]==0){
							check[i]=1;
							q.push(i);
							v[i]->prenum=inum;
							v[i]->token=1;
							v[i]->con=min(v[inum]->con,ma[i][inum]);
						}
					}
					check[inum]=2;
		
			
			}
		
		if(flag){
		
			int j=dest;
			while(j!=0){
				int be=v[j]->prenum;
				if(v[j]->token==0) {
				
					ma[be][j]+=v[dest]->con;
				}
				else {
		
					ma[j][be]-=v[dest]->con;
				}
				j=be; 
			}
		}
		}
		
	}
}

• Re:wa 了无数次 为什么就不对呢 ？？？请求指出思路上有什么问题.. (14) DeSMoon 2009-07-28 20:29:59
  • Re:wa 了无数次 为什么就不对呢 ？？？请求指出思路上有什么问题.. (26) _leaf_ 2009-07-29 00:55:30
• Re:wa 了无数次 为什么就不对呢 ？？？请求指出思路上有什么问题.. (216) pas_zoujp 2010-03-22 21:14:09