基于圖論的獎金分配問題
#include
#include
#include
#include
#include
#define nil NULL // 請忽略這些,這些是模板
#define N 10000
using namespace std;
ifstream fin ("reward.in");
ofstream fout ("reward.out");
class link
{
public:
long dex;
link*next;
link (long xx=0,link*nn=nil)
{
dex=xx;
next=nn;
}
}*t[N+1],*gt[N+1];
long n,m;
long c[N+1],col[N+1];
bool b[N+1];
static inline void join(link*&a,long b)
{
link*p=new link(b,a);
a=p;
}
bool flag;
static inline void dfs(long dex)
{
col[dex]=1;
for (link*p=t[dex];p&&flag;p=p->next)
if (col[p->dex]==0)
dfs(p->dex);
else if (col[p->dex]==1) // 有環(huán)
flag=false;
col[dex]=2;
c[m--]=dex;
}
static inline void mon(long dex)
{
for (link*p=t[dex];p;p=p->next)
if (col[p->dex]dex]=col[dex]+1;
mon(p->dex);
}
}
static inline bool ok(long dex)
{
if (b[dex]) return false;
col[dex]--;
if (col[dex]>=0)
{
long flag=true;
for (link*p=gt[dex];p&&flag;p=p->next)
if ((col[p->dex]dex)));
else flag=false;
if (flag) return true;
}
col[dex]++;
b[dex]=true;
return false;
}
int main(int argc,char *argv[])
{
fin >> n >> m;
for (long i=1;i x >> y;
join(t[y],x);
join(gt[x],y);
}
memset(c,0,sizeof(c));
memset(col,0,sizeof(col));
m=n;
flag=true;
for (long i=1;i